Lecture 04: Recursion CS 112: Object-Oriented Programming
Recursion
Dr. Zahid Halim
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
Lecture 04: Recursion CS 112: Object-Oriented Programming
Recursion Defined
Recursion is a technique for defining data structures or
algorithms in terms of themselves. A recursive
algorithm is a form of decomposition where rather than
choosing an arbitrary subtask of the problem to do,
choose a simpler problem that has the same form as
the original (self-similarity). A recursive definition has
two parts:
– the base case - a stopping condition
– the recursive step - an expression of the computation or
definition in terms of itself
There may be one or more of each of these.
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
Lecture 04: Recursion CS 112: Object-Oriented Programming
Example of a Recursive Definition
• There are many recursive definitions in mathematics.
Consider the factorial function:
n! = n * (n-1) * (n -2) * … * 2 * 1
• The same function can be defined recursively by
giving a base case and a recursive step:
0! = 1 (by definition)
n! = n * (n - 1)! (the recursive step)
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
Lecture 04: Recursion CS 112: Object-Oriented Programming
Recursive Functions
A recursive function is a function which calls itself somewhere in
the function body. Recursive functions are supported in most
modern programming languages including C++
A language that supports recursion usually requires a system
stack for tracking function call and return.
In a recursive function, execution must “drive” computation to a
base case so the recursion will stop. The recursive step is
intended to ensure that the computation eventually terminates.
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
Lecture 04: Recursion CS 112: Object-Oriented Programming
The Factorial Function
The recursive definition for factorial can be written in a very
straightforward manner. Take some time to convince yourself that
this method works:
int fact(int n)
{
if (n < 2) // terminal case
return 1;
else // recursive step
return (n * fact(n - 1));
}
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
Lecture 04: Recursion CS 112: Object-Oriented Programming
Tracing a Recursive Function
The behavior of fact when n = 5:
fact(5) -> 5 * fact(4)
fact(4) -> 4 * fact(3)
fact(3) -> 3 * fact(2)
fact(2) -> 2 * fact(1)
fact(1) -> 1
We can view this as a process of driving the
computation to the base case; next, we slow down.
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
Lecture 04: Recursion CS 112: Object-Oriented Programming
Tracing a Recursive Function
Eventually, the call fact(1) returns 1 to the function
which called it, so that it can complete its calculation
and return its result to the function which called it, and
so on. This is called back-substitution, or unwinding the
recursion.
fact(1) -> 1
fact(2) -> 2 * 1 = 2
fact(3) -> 3 * 2 = 6
fact(4) -> 4 * 6 = 24
fact(5) -> 5 * 24 = 120 <<< the final answer
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
Lecture 04: Recursion CS 112: Object-Oriented Programming
Recursion Under the Hood
The execution environment sets up a call stack (or system stack)
to store activation records for keeping track of function call and
return. Therefore, each recursive call is represented by an
activation record on the stack. The activation record at the top
of the stack is active, and all other calls on the stack are said
to be suspended. Each recursive-step call waits for the results of
the next call so it can finish its own computation.
In geeneral, recursion works by taking advantage of the
system stack to keep track of the partial results computed by the
successive recursive calls; these partial results are then back-
substituted into the preceding calls through the normal operation
of return values.
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
Lecture 04: Recursion CS 112: Object-Oriented Programming
Example Using Recursion: The Fibonacci Series
• Fibonacci series: 0, 1, 1, 2, 3, 5, 8...
– Each number sum of two previous ones
– Example of a recursive formula:
fib(n) = fib(n-1) + fib(n-2)
• C++ code for fibonacci function
long fibonacci( long n )
{
if ( n == 0 || n == 1 ) // base case
return n;
else return fibonacci( n - 1 ) + fibonacci( n – 2 );
}
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
Lecture 04: Recursion CS 112: Object-Oriented Programming
Example Using Recursion: The Fibonacci Series
• Diagram of Fibonnaci function
f( 3 )
return f( 2 ) + f( 1 )
return f( 1 ) + f( 0 ) return 1
return 1 return 0
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
1// Fig. 3.15: fig03_15.cpp
2// Recursive fibonacci function
3 #include <iostream>
4
5using std::cout;
6using std::cin;
7 using std::endl;
8
9unsigned long fibonacci( unsigned long );
10
11 int main()
12 {
13 unsigned long result, number;
14
15 cout << "Enter an integer: ";
16 cin >> number;
17 result = fibonacci( number );
18 cout << "Fibonacci(" << number << ") = " << result << endl;
19 return 0;
20 }
21
22 // Recursive definition of function fibonacci
23 unsigned long fibonacci( unsigned long n )
Only the base cases return
24 {
values. All other cases call
25 if ( n == 0 || n == 1 ) // base case
26 return n;
the fibonacci function
27 else // recursive case again.
28 return fibonacci( n - 1 ) + fibonacci( n - 2 );
29 }
Enter an integer: 0
Fibonacci(0) = 0
Enter an integer: 1
Fibonacci(1) = 1
Enter an integer: 2
Fibonacci(2) = 1
Enter an integer: 3
Fibonacci(3) = 2
Enter an integer: 4
Fibonacci(4) = 3
Enter an integer: 5
Fibonacci(5) = 5
Enter an integer: 10
Fibonacci(10) = 55
Enter an integer: 6
Fibonacci(6) = 8
Enter an integer: 20
Fibonacci(20) = 6765
Enter an integer: 30
Fibonacci(30) = 832040
Enter an integer: 35
Fibonacci(35) = 9227465
Lecture 04: Recursion CS 112: Object-Oriented Programming
Recursion vs. Iteration
• Repetition
– Iteration: explicit loop
– Recursion: repeated function calls
• Termination
– Iteration: loop condition fails
– Recursion: base case recognized
• Both can have infinite loops
• Balance between performance (iteration) and good
software engineering (recursion)
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
Lecture 04: Recursion CS 112: Object-Oriented Programming
References
• Book Code: A
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
