Skip to content
GATETECH
Official PYQ · 2005Q81bRecursionMCQ1 mark

GATE CS 2005 Q81b — Recursion

Explain with AI
double foo(int n)
{
    int i;
    double sum;
    if(n == 0)
    {
        return 1.0;
    }
    else
    {
        sum = 0.0;
        for(i = 0; i < n; i++)
        {
            sum += foo(i);
        }
        return sum;
    }

}

Suppose we modify the above function foo()foo() and stores the value of foo(i) 0≤i<nfoo(i) \ 0 \leq i < n, as and when they are computed. With this modification the time complexity for function foo()foo() is significantly reduced. The space complexity of the modified function would be:

Choose one option
View worked solution

Answer: B

The question describes a memoization (dynamic programming) approach to optimize the recursive function foo().

1. Memoization Table Space

To store the computed values of foo(i)foo(i) for 0≤i<n0 \le i < n, we need a table (such as an array) of size nn. This requires:

Table Space=O(n)\text{Table Space} = O(n)

2. Recursion Stack Space

To compute foo(n)foo(n), the function recursively calls foo(n−1)foo(n-1), which in turn calls foo(n−2)foo(n-2), and so on, down to the base case foo(0)foo(0).

  • The maximum depth of the recursion stack is nn.
  • Therefore, the space required by the call stack is O(n)O(n).

Conclusion

Combining the space required for the memoization table and the recursion stack:

Total Space Complexity=O(n)+O(n)=O(n)\text{Total Space Complexity} = O(n) + O(n) = O(n)

Hence, the correct option is B.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Recursion questions