Test: Recursion- 1 - Computer Science Engineering (CSE) MCQ

Here d is Static, so the value of d will persists between the function calls.

1. count(3) will print the value of n and d and increments d and call count(2) = prints 3 1.
2. count(2) will print the value of n and d and increments d and call count(1) = prints 2 2.
3. count(1) will print the value of n and d and increments d => prints 1 3.

Now it will return and prints the final incremented value of d which is 4, 3 times.
So, option A is correct = 3 1 2 2 1 3 4 4 4

concat(a,head(tail(tail(acbc))))
concat(a,head(tail(cbc)))
concat(a,head(bc))
concat(a,b)
ab.

Function Flow:

• Starts with n = 1 and i = 1 (static).
• Adds i to n and increments i recursively until n >= 5.

Steps:
We start with n = 1 and i = 1.

            First Call: f(1)

• Initial values: n = 1, i = 1.
• Condition: n >= 5 → False.
• Update n: n = n + i = 1 + 1 = 2.
• Increment i: i = 2.
• Recursive call: f(2).

           Second Call: f(2)

Third Call: f(4)

Fourth Call: f(7)

• Initial values: n = 2, i = 2 (retained from the previous call).
• Condition: n >= 5 → False.
• Update n: n = n + i = 2 + 2 = 4.
• Increment i: i = 3.
• Recursive call: f(4).
• Initial values: n = 4, i = 3 (retained from the previous call).
• Condition: n >= 5 → False.
• Update n: n = n + i = 4 + 3 = 7.
• Increment i: i = 4.
• Recursive call: f(7).
• Initial values: n = 7, i = 4 (retained from the previous call).
• Condition: n >= 5 → True.
• Return value: n = 7.

  Once the base case is met (n = 7), the recursion stops. Each recursive call returns the same value (7) back up the chain:

• The third call (f(4)) returns 7.
• The second call (f(2)) returns 7.
• The first call (f(1)) returns 7

  Answer:

  (c) 7

A. The code here is storing only local variables. So, the space complexity will be the recursion depth- maximum happening for the last iteration of the for loop- foo(n-1) - foo(n-2) - .... - foo(0) all live giving space complexity O(n).

B. To store the n values we need space complexity O(n). So, the space complexity won't change and will be O(n).

The modification being proposed is tabulation method of Dynamic Programming.
So let we have an auxillary array which stores the value of foo(i) once it is computed and can be used at later stage .So foo(i) is not called again , instead lookup from the table takes place. It would be something like :

#include <stdio.h>
#define max 1000
int foo[max];

foo(int n) {
if(foo[n] == -1) //compute it and store at foo[n] and return
else // return foo[n] directly
}

int main(void) {
//initialize all elements of foo[max] to -1
return 0;
}Using this approach , we need an auxillary array of size n to store foo(i) where i ranges from 0 to n-1.

So space complexity of this method = O(n) And function foo(n) computes 2^{n - 1}    

f(5) = 18.
f(3) + 2 = 16 + 2 = 18
f(2) + 5 = 11 + 5 = 16

f(1) + 5 = 6 + 5 = 11
f(0) + 5 = 1+5 = 6
Consider from last to first. Since it is recursive function.

The function terminates for all powers of 2 (which is infinite), hence (i) is false and (ii) is TRUE.
Let n = 5.
Now, recursive calls will go like 5 - 14 - 7 - 20 - 10 - 5 -
And this goes into infinite recursion. And if we multiply 5 with any power of 2, also result will be infinite recursion. Since, there are infinite powers of 2 possible, there are infinite recursions possible (even considering this case only). So, (iv) is TRUE and (iii) is false.
So, correct answer is (D)

• Unroll recursion up to a point where we can distinguish the given options and choose the correct one!
• Options B and D are eliminated.
• A is the answer.

Answer is A) w and 0

If we solve using parallel innermost rule
F(1,0) = F(2,F(1,0)) * F(0,F(1,0))

=F(2, F(2,F(1,0)) * F(0,F(1,0)) ) * F(0, F(2,F(1,0)) * F(0,F(1,0)) )

Since computation of F(1,0) goes on
we assign F(1,0) to w
So F(1,0)= w

Using parallel outermost rule
F(1,0)= F(2,F(1,0)) * F(0,F(1,0))
= F(2,F(1,0)) * 0
= 0

Computable function: those which can be incorporated in a program using for/while loops.

Total Function: Defined for all possible inputs
Well Defined: if its definition assigns it a unique value.

It was a belief in early 1900s that every Computable function was also Primitively Recursive. But the discovery of Ackermann function provided a counter to it.
The class of primitive recursive functions is a small subclass of the class of recursive functions. This means that there are some functions which are Well-Defined Total Functions and are Computable BUT Not primitively recursive; eg. Ackermann function.

This makes all options from option A to option D as True.
But option E as
. As iterative programs are equivalent to only Primitively Recursive class.