What is the recursion base case in the binary search algorithm?
Binary search terminates when low exceeds high or when the target element matches mid.
What is the output of calling show(3)?
#include <stdio.h>
void show(int n) {
if (n <= 0) return;
show(n - 1);
show(n - 1);
printf("%d ", n);
}Post-order traversal printing: show(1) prints 1. show(2) prints 1 1 2. show(3) prints 1 1 2 1 1 2 3.
What is the complexity of computing Fibonacci numbers recursively without memoization?
Without memoization, overlapping subproblems generate an exponential call tree $O(2^n)$.
What is the output of the following C program?
#include <stdio.h>
int f(int n) {
if (n == 0) return 0;
return n + f(n - 1);
}
int main(void) {
printf("%d", f(10));
return 0;
}Sum of first 10 integers: 10 * 11 / 2 = 55.
In C, what occurs if a recursive function modifies a global variable?
Global variables reside in the static data segment and share a single memory address across all function activation frames.