GATE Computer Science Engineering(CSE) 2027 Test: Recursion- 1 Free Online

Option A is correct: 3 1 2 2 1 3 4 4 4

static int d = 1 is initialized once and retains its value across all calls to the function.

Call 1: n = 3, d = 1. The function prints 3 1, then increments d to 2 and calls count(2).

Call 2: n = 2, d = 2. It prints 2 2, increments d to 3 and calls count(1).

Call 3: n = 1, d = 3. It prints 1 3, increments d to 4. The if condition is false, so it does not recurse; the printf after the if prints 4 for this call.

Returning to Call 2, the printf after the recursive call prints the current d = 4. Returning to Call 1, its final printf also prints the current d = 4.

Putting all prints in chronological order yields: 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}    

Option D is correct; f(5) = 18.

Call f(5). Since n > 3, the code sets r = 5 and returns f(3) + 2.

Compute f(3). Here n = 3 is not > 3, so the function returns f(2) + r. The static variable r retains the value 5.

f(0) = 1 by the base case.

f(1) = f(0) + r = 1 + 5 = 6.

f(2) = f(1) + r = 6 + 5 = 11.

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

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

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