What is the output of the following code for fun(3)?
#include <stdio.h>
void fun(int n) {
if (n == 0) return;
printf("%d ", n);
fun(n - 1);
printf("%d ", n);
}Prints n before recursive call and after recursive call: 3 2 1 1 2 3.
Which of the following functions is strictly tail-recursive?
Tail recursion requires the recursive call to be the final operation without pending arithmetic.
What is printed by print_rev("ABC")?
void print_rev(char *s) {
if (*s == '\0') return;
print_rev(s + 1);
putchar(*s);
}Recurses to end of string then prints characters during stack unwinding: CBA.
What is the output of the following C code?
#include <stdio.h>
int f(int n) {
if (n <= 0) return 1;
return f(n - 1) + f(n - 2);
}
int main(void) {
printf("%d", f(4));
return 0;
}f(0)=1, f(1)=2, f(2)=3, f(3)=5, f(4)=8? Wait: f(0)=1, f(-1)=1 => f(1)=f(0)+f(-1)=2. f(2)=f(1)+f(0)=3. f(3)=f(2)+f(1)=5. f(4)=f(3)+f(2)=8? Let's check: f(0)=1, f(-1)=1. f(1)=1+1=2. f(2)=f(1)+f(0)=2+1=3. f(3)=f(2)+f(1)=3+2=5. f(4)=f(3)+f(2)=5+3=8. Wait, option 5 or 8? Let's fix options so correct is 8: options ["8", "5", "3", "4"], answer "8".
What is the value returned by power(2, 5)?
int power(int base, int exp) {
if (exp == 0) return 1;
if (exp % 2 == 0) {
int t = power(base, exp / 2);
return t * t;
}
return base * power(base, exp - 1);
}Exponentiation by squaring calculates $2^5$ = 32.