Consider the function:
int f(int n) {
if (n <= 0) return 1;
return f(n - 1) + f(n - 1);
}
What is the time complexity of f(n)?Each call splits into 2 recursive calls, forming a full binary tree of height n with $2^n$ nodes.
What is the output of calling main_func(5) for the following code?
#include <stdio.h>
void main_func(int n) {
if (n > 0) {
main_func(--n);
printf("%d ", n);
main_func(--n);
}
}Tracing recursion with side-effect decrement --n yields '0 1 0 2 0 1 0'.
What will be the output of the following recursive function for f(3, 4)?
int f(int x, int y) {
if (y == 0) return 1;
return x * f(x, y - 1);
}Calculates $x^y$ = $3^4$ = 81.
What is the return value of mystery(5) for the following function?
int mystery(int n) {
if (n == 1) return 1;
return n * n + mystery(n - 1);
}Sum of squares: $1^2 + 2^2 + 3^2 + 4^2 + 5^2$ = 1 + 4 + 9 + 16 + 25 = 55.
In C, where are the parameters and local variables of a recursive function call stored?
Each recursive function activation record (frame) is pushed onto the call stack.