What will be the output of calling test(3) for the C function below?
#include <stdio.h>
void test(int n) {
if (n > 0) {
printf("%d ", n);
test(n - 1);
test(n - 1);
}
}test(3): prints 3, calls test(2), then test(2).
test(2): prints 2, calls test(1), then test(1).
test(1): prints 1.
Output sequence: 3 2 1 1 2 1 1.
What is the maximum stack depth (number of stack frames) created when executing recursive factorial(n)?
Including the base case call factorial(0), there are n + 1 active stack frames.
Consider the following recursive function with a static variable:
int fun(int n) {
static int x = 1;
if (n <= 1) return 1;
x++;
return fun(n - 1) + x;
}What does fun(4) return?
fun(4): x becomes 2, calls fun(3).
fun(3): x becomes 3, calls fun(2).
fun(2): x becomes 4, calls fun(1).
fun(1): returns 1.
fun(2) returns 1 + 4 = 5.
fun(3) returns 5 + 4 = 9.
fun(4) returns 9 + 4? Note: x is shared static = 4 at the end. So unwinding adds x = 4 at each level: fun(1)=1, fun(2)=1+4=5, fun(3)=5+4=9, fun(4)=9+4=13? Wait, let's trace carefully: x starts 1. fun(4)->x=2; fun(3)->x=3; fun(2)->x=4; fun(1)->1. When fun(2) evaluates fun(1) + x, x is 4, returning 1+4=5. Next fun(3) evaluates fun(2) + x, x is 4, returning 5+4=9. Next fun(4) evaluates fun(3) + x, x is 4, returning 9+4=13. Wait, let's re-verify: fun(4) = 13. Options: 13 is option C.
Which of the following optimization techniques enables a compiler to reuse the current stack frame for recursive calls?
Tail Call Optimization (TCO) allows tail-recursive function calls to overwrite the current stack frame instead of pushing a new frame.
What is the output of the following C program?
#include <stdio.h>
void p(int n) {
if (n > 0) {
p(n - 1);
printf("%d ", n);
p(n - 1);
}
}
int main(void) {
p(3);
return 0;
}p(1) prints '1'.
p(2) calls p(1), prints '2', calls p(1) -> '1 2 1'.
p(3) calls p(2), prints '3', calls p(2) -> '1 2 1 3 1 2 1'.