Skip to content
GATETECH
Official PYQ · 2009Q18Algorithm Design: Dynamic ProgrammingMCQ1 mark

GATE CS 2009 Q18 — Algorithm Design: Dynamic Programming

Explain with AI

Consider the program below:

#include <stdio.h>
int fun(int n, int *f_p) {
    int t, f;
    if (n <= 1) {
        *f_p = 1;
        return 1;
    }
    t = fun(n-1, f_p);
    f = t + *f_p;
    *f_p = t;
    return f;
}

int main() {
    int x = 15;
    printf("%d/n", fun(5, &x));
    return 0;
}

The value printed is:

Choose one option
View worked solution

Answer: B

To find the value printed by the program, we trace the execution of the recursive function call fun(5, &x).

Since f_p is a pointer to the variable x in the main function, all recursive calls share and modify the same memory location x. Let's trace the calls down to the base case and then propagate back up:

1. Downward Recursion Phase

  • fun(5, &x) calls fun(4, &x)
  • fun(4, &x) calls fun(3, &x)
  • fun(3, &x) calls fun(2, &x)
  • fun(2, &x) calls fun(1, &x)

2. Upward Return Phase

  • At fun(1, &x):
    • Since n≤1n \le 1, the base case is triggered.
    • *f_p = 1 (so x becomes 11).
    • Returns 11.
  • At fun(2, &x):
    • t = fun(1, &x) = 1. At this point, *f_p (which is x) is 11.
    • f = t + *f_p = 1 + 1 = 2.
    • *f_p = t = 1 (so x becomes 11).
    • Returns f = 2.
  • At fun(3, &x):
    • t = fun(2, &x) = 2. At this point, *f_p (which is x) is 11.
    • f = t + *f_p = 2 + 1 = 3.
    • *f_p = t = 2 (so x becomes 22).
    • Returns f = 3.
  • At fun(4, &x):
    • t = fun(3, &x) = 3. At this point, *f_p (which is x) is 22.
    • f = t + *f_p = 3 + 2 = 5.
    • *f_p = t = 3 (so x becomes 33).
    • Returns f = 5.
  • At fun(5, &x):
    • t = fun(4, &x) = 5. At this point, *f_p (which is x) is 33.
    • f = t + *f_p = 5 + 3 = 8.
    • *f_p = t = 5 (so x becomes 55).
    • Returns f = 8.

Thus, the function fun(5, &x) returns 8, which is then printed by printf.

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

Published
Report a correction
Keep exploringMore Algorithm Design: Dynamic Programming questions