Source: Exam 2 Key, University of Central Florida
Tags: recursion, recursive functions, base case, infinite recursion, call stack, stack overflow, recurrence relations, iterative substitution, big-oh, time complexity, C programming
Difficulty: Intermediate Prerequisites: Familiarity with C functions, variables and scope, basic loop constructs, and introductory big-O notation.
Recursion is one of the core problem-solving strategies in computer science, and this exam covers it from both the conceptual and analytical sides. You need to understand how recursive calls work mechanically in C (the call stack, local variable scope, base cases), how to trace through recursive code to predict output, and how to set up and solve recurrence relations that describe the running time of recursive algorithms. If you are comfortable writing loops but have not yet internalised how function calls nest, start there before tackling recurrence relations.
A recursive function calls itself with a smaller or simpler input until it hits a base case that stops the chain. Each call gets its own local variables on the stack. To analyse running time, you express the work as a recurrence relation and solve it, usually by iterative substitution, to get a big-O bound.
Base case
The condition under which a recursive function stops calling itself and returns directly. Think of it as the "exit door" that prevents infinite recursion.
Recursive case
The branch of the function where it calls itself with modified arguments, moving closer to the base case with each call.
Infinite recursion
What happens when a recursive function never reaches a base case. The calls keep stacking up until the program runs out of stack memory and crashes.
Stack overflow
The runtime error that results from infinite (or excessively deep) recursion. Each call consumes stack space, and when that space is exhausted the program terminates. In simple terms, this is what "blowing the stack" means.
Call stack
The region of memory where each function call's local variables, parameters, and return address are stored. Every new recursive call adds a frame; every return removes one. This is why recursive functions use more memory than iterative equivalents.
Mutual recursion
Two or more functions that call each other in a cycle (e.g. func1 calls func2, func2 calls func1). If there is no base case in either function, this produces infinite recursion just like a single self-calling function would.
Recurrence relation
A mathematical equation that expresses the running time of a recursive algorithm in terms of the running time on smaller inputs, e.g. T(n) = T(n-1) + 1. Think of it as a recipe that says "the cost for input n equals the cost for a smaller input plus some extra work."
Iterative substitution (expansion method)
A technique for solving recurrence relations by repeatedly replacing the recursive term with its definition until a pattern emerges. You then write a general formula, substitute the base-case value of k, and simplify to get a closed-form expression.
Big-O (big-oh) notation
An upper bound on the growth rate of a function. O(n) means the running time grows at most linearly, O(n^2) means at most quadratically, and so on.
Each recursive call creates a new stack frame with its own copy of all local variables. Local variables are not shared across calls.
A recursive function can call itself more than once in the same invocation (e.g. the Fibonacci function calls fib(n-1) and fib(n-2)).
You can make a recursive call to main() from inside main() in C. It is legal, though rarely practical.
Recursion is not limited to a function calling itself directly. Two functions can call each other (mutual recursion), and this will also recurse infinitely if neither contains a working base case.
Every correct recursive function must eventually reach a base case. Without one, the function recurses until a stack overflow kills the process at runtime, not at compile time.
The base case does not need to be at the top of the function, but placing it there is the clearest pattern and the one expected on exams.
When the recursive call happens before a print statement, the printing occurs on the way back up the call stack, which reverses the apparent order.
Example:
void printNumbers(int n) {
if (n == 0) return;
printNumbers(n - 1);
printf("%d ", n);
}
Calling printNumbers(3) prints 1 2 3, not 3 2 1, because each call waits for the deeper call to finish before it prints its own value of n.
Example:
int sum(int n) {
if (n == 0) return 0;
return n + sum(n - 1);
}
sum(3) computes 3 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0) = 3 + 2 + 1 + 0 = 6.
Recursion involves extra time and memory overhead because of the function call stack. Each call requires pushing a new frame, and each return requires popping it.
An iterative solution using a loop will typically use O(1) extra memory for the same task, whereas the recursive version uses O(n) stack space for n calls deep.
Recursion is not always slower in wall-clock terms, but the overhead is a real and testable disadvantage.
Three exam-style coding problems appeared. The pattern for all of them is the same: identify the base case, handle it, then express the answer in terms of a recursive call on a smaller input.
int countDigits(int n) {
if (n < 10) return 1;
return 1 + countDigits(n / 10);
}
Base case: a single digit (n < 10) has 1 digit. Recursive case: strip the last digit with integer division and add 1.
double recMin(double arr[], int first, int last) {
if (first == last)
return arr[first];
double minForRest = recMin(arr, first + 1, last);
if (arr[first] < minForRest)
return arr[first];
return minForRest;
}
Base case: one element. Recursive case: find the min of the rest, then compare it with the current element.
float recMax(float arr[], int first, int last) {
if (first == last)
return arr[first];
double maxForRest = recMax(arr, first + 1, last);
if (arr[first] > maxForRest)
return arr[first];
return maxForRest;
}
Same structure as recMin, with the comparison flipped.
A recursive factorial (one recursive call, constant work per call): T(n) = T(n-1) + 1
A recursive function that does O(n) work and calls itself once on half the input: T(n) = T(n/2) + n (binary-search style, but with linear work added)
The naive recursive Fibonacci (two recursive calls): T(n) = T(n-1) + T(n-2) + 1
Recursive binary search (one call on half the input, constant work): T(n) = T(n/2) + c
The method works by expanding the recurrence step by step until you spot a pattern, then writing the general term after k iterations, choosing k so that the recursive term hits the base case, and simplifying.
Example 1: T(1) = 1, T(n) = T(n-1) + c
Expand: T(n) = T(n-2) + 2c = T(n-3) + 3c = ... = T(1) + (n-1)c = 1 + (n-1)c.
Big-oh: O(n).
Example 2: T(1) = 0, T(n) = T(n/2) + 1
Expand: T(n) = T(n/4) + 2 = T(n/8) + 3 = ... After k steps, T(n) = T(n/2^k) + k. Set n/2^k = 1, so k = log₂ n.
T(n) = 0 + log₂ n.
Big-oh: O(log n).
Example 3: T(1) = 1, T(n) = T(n-1) + n
Expand: T(n) = T(n-2) + (n-1) + n = ... = T(1) + 2 + 3 + ... + n = 1 + n(n+1)/2 - 1 = n(n+1)/2.
Big-oh: O(n²).
Example 4: T(1) = 1, T(n) = 2T(n/2) + n²
After k iterations: T(n) = 2^k T(n/2^k) + n²(1 + 1/2 + 1/4 + ... + 1/2^(k-1)).
The geometric sum converges to a constant close to 2. Set k = log₂ n:
T(n) = n · T(1) + c · n² = n + c · n².
Big-oh: O(n²).
Example 5: T(1) = 1, T(n) = 2T(n/2) + n
After k iterations: T(n) = 2^k T(n/2^k) + kn. Set k = log₂ n:
T(n) = n · T(1) + n · log₂ n = n + n log₂ n.
Big-oh: O(n log n).
Common recurrence–complexity pairings:
Recurrence | Closed Form | Big-O |
|---|---|---|
T(n) = T(n-1) + 1 | O(n) | Linear |
T(n) = T(n-1) + n | O(n²) | Quadratic |
T(n) = T(n/2) + 1 | O(log n) | Logarithmic |
T(n) = T(n/2) + c | O(log n) | Logarithmic |
T(n) = 2T(n/2) + n | O(n log n) | Linearithmic |
T(n) = 2T(n/2) + n² | O(n²) | Quadratic |
T(n) = T(n-1) + T(n-2) + 1 | O(2^n) approx. | Exponential |
Geometric series (used in iterative substitution):
1 + 1/2 + 1/4 + ... + 1/2^(k-1) converges to a value less than 2 as k grows. Treat this sum as a constant when it appears in a recurrence solution.
Recursion is the engine behind divide-and-conquer algorithms such as merge sort and quicksort, both of which split a problem in half and recombine results. The recurrence T(n) = 2T(n/2) + n describes merge sort's running time exactly, which is why understanding iterative substitution matters beyond the exam.
Students often believe that local variables in a recursive function are shared between calls. They are not; each call gets its own stack frame with independent copies.
Students sometimes think a missing base case will cause a compile-time error. It will not. The code compiles fine and crashes at runtime with a stack overflow.
Many students confuse the recurrence for a factorial implementation (T(n) = T(n-1) + 1, which is O(n)) with the value computed by factorial (n!, which grows much faster). The recurrence counts operations, not the result.
When print statements appear after the recursive call, students frequently predict the output in the wrong order. The print happens on the way back up the stack, not on the way down.
⚠️ Tracing recursive output (especially when the print is after the recursive call) is a recurring exam question. Practice until you can do it without writing out every frame.
⚠️ Know the recurrence relation for factorial (T(n) = T(n-1) + 1), Fibonacci (T(n) = T(n-1) + T(n-2) + 1), and binary search (T(n) = T(n/2) + c) cold.
⚠️ The iterative substitution method is tested as both a multiple-choice concept question and as a full worked essay. You must show your expansion steps clearly for full marks.
⚠️ Sorted List Matching Problem (SLMP) solution complexities: brute force is O(n²), binary search per element is O(n log n), simultaneous two-pointer traversal is O(n).
True or false: local variables in a recursive C function are shared across all recursive calls. (False)
True or false: a recursive function must eventually reach a base case to avoid infinite recursion. (True)
Fill in the blank: if a recursive function has no base case, it will cause a __________ at runtime. (stack overflow)
True or false: recursive functions use less memory than their iterative equivalents. (False)
The recurrence T(n) = T(n-1) + c, where c is a constant, solves to O(___). (n)
Q: What will printNumbers(3) output if the function recurses first and prints second (print after recursive call)?
A: 1 2 3. The recursive calls reach the base case first, then each frame prints its value of n as the stack unwinds.
Q: What is the output of printf("%d\n", sum(3)); where sum(n) returns 0 if n == 0, and n + sum(n-1) otherwise?
A: 6. The computation is 3 + 2 + 1 + 0 = 6.
Q: What happens if a recursive function does not have a base case?
A: It will cause a stack overflow at runtime. It does not produce a compile-time error.
Q: Which of the following is a disadvantage of recursion over iteration?
A: Recursion involves extra time and memory overhead due to the function call stack.
Q: What is the recurrence relation for a typical recursive factorial implementation?
A: T(n) = T(n-1) + 1. Each call does constant work and makes one recursive call on n-1.
Q: Solve T(1) = 1, T(n) = 2T(n/2) + n by iterative substitution. What is the big-oh?
A: After k expansions, T(n) = 2^k T(n/2^k) + kn. Set k = log₂ n to get T(n) = n + n log₂ n. Big-oh is O(n log n).
Q: Solve T(1) = 1, T(n) = 2T(n/2) + n². What is the big-oh?
A: After k expansions, the non-recursive terms form a geometric series that converges to a constant times n². T(n) = n + c·n². Big-oh is O(n²).
Q: Write a recursive function countDigits(int n) that returns the number of digits in a non-negative integer.
A: Base case: if n < 10, return 1. Recursive case: return 1 + countDigits(n / 10).
This material connects directly to sorting algorithms (merge sort and quicksort are recursive, and their analysis uses the same recurrence-solving techniques). It also sets the groundwork for tree traversals later in the course, which are naturally recursive. The linked-list manipulation questions on this same exam blend recursion with pointer work, so make sure you are comfortable with both.
recursion, recursive function, base case, recursive case, infinite recursion, stack overflow, call stack, stack frame, mutual recursion, recurrence relation, iterative substitution, expansion method, big-oh, big-O, O(n), O(n²), O(log n), O(n log n), divide and conquer, factorial recursion, Fibonacci recursion, binary search recurrence, sorted list matching problem, SLMP, COP 3502, Computer Science I, UCF, C programming, exam 2 review