Recursive Definitions and Function Calls: A Brief Overview with Examples
1. Recursive Definitions
Recursion is a fundamental concept in computer science where a function calls itself to solve a problem
by breaking it down into smaller, more manageable subproblems. Recursive definitions consist of two
key parts:
Base Case (Anchor/Ground Case) : The simplest case that can be solved directly without further
recursion.
Inductive Step : A rule or set of rules that reduces the problem to a simpler version of itself.
Example 1: Factorial Function
The factorial of a non-negative integer n is defined as:
n!={
n⋅(n−1)!
if n=0
if n>0
Base Case : n=0, where 0!=1.
Inductive Step : For n>0, compute n⋅(n−1)!.
Recursive Implementation in C++:
unsigned int factorial(unsigned int n) {
if (n == 0) {
return 1; // Base case
} else {
return n * factorial(n - 1); // Inductive step
}
Example 2: Fibonacci Sequence
The Fibonacci sequence is defined as:
F(n)=
F(n−1)+F(n−2)
if n=0
if n=1
if n>1
Base Cases : F(0)=0 and F(1)=1.
Inductive Step : For n>1, compute F(n−1)+F(n−2).
Recursive Implementation in C++:
unsigned int fibonacci(unsigned int n) {
if (n == 0) {
return 0; // Base case
} else if (n == 1) {
return 1; // Base case
} else {
return fibonacci(n - 1) + fibonacci(n - 2); // Inductive step
2. Function Calls and Recursion Implementation
When a function is called recursively, the system uses a runtime stack to manage the state of each
function call. Each recursive call creates a new activation record (or stack frame) on the runtime stack,
which contains:
Parameters passed to the function.
Local variables.
Return address (where execution resumes after the function returns).
Dynamic link (pointer to the caller's activation record).
Example: Factorial Function Execution
Consider the recursive call factorial(3):
Initial Call : factorial(3)
Activation record for factorial(3) is pushed onto the stack.
Since n=3
=0, the function calls factorial(2).
Second Call : factorial(2)
Activation record for factorial(2) is pushed onto the stack.
Since n=2
=0, the function calls factorial(1).
Third Call : factorial(1)
Activation record for factorial(1) is pushed onto the stack.
Since n=1
=0, the function calls factorial(0).
Fourth Call : factorial(0)
Activation record for factorial(0) is pushed onto the stack.
Since n=0, the base case is reached, and the function returns 1.
As each activation record is popped off the stack, the results are combined:
factorial(0) returns 1.
factorial(1) computes 1⋅1=1 and returns 1.
factorial(2) computes 2⋅1=2 and returns 2.
factorial(3) computes 3⋅2=6 and returns 6.
Runtime Stack Visualization
Here’s how the runtime stack looks during the execution of factorial(3):
Here’s how the runtime stack looks during the execution of factorial(3):
STACK FRAME
PARAMETERS
LOCAL VARIABLES
RETURN ADDRESS
factorial(3)
n=3
factorial(2)
n=2
factorial(1)
n=1
factorial(0)
n=0
When factorial(0) returns, the stack unwinds, and each frame is popped off as the results are computed
3. Activation Records
Each activation record contains:
Parameters and Local Variables : Values passed to the function and local variables declared within it.
Return Address : The memory address where execution resumes after the function returns.
Dynamic Link : Pointer to the caller's activation record.
Return Value : The value returned by the function.
Example: Activation Record for factorial(3)
When factorial(3) is called:
Activation Record for factorial(3) :
Parameters: n = 3
Local Variables: None
Return Address: Address of the next instruction after the call
Dynamic Link: Pointer to the activation record of the caller (e.g., main())
As each recursive call is made, a new activation record is created, and the stack grows. When the base
case is reached, the stack starts to unwind, and the results are propagated back up the call chain.
