CMP1040: Data Structures and Algorithms
Lecture 01: Recursion
Ahmed Hamdy
Computer Engineering Department
Cairo University
Agenda
• Function calling itself!!
• Recursion definition and types
• Factorial
• Fibonacci
• 𝑪𝑛𝑘
• Tower of Hanoi
Simple Foo
• What will happen with the following?
foo(1): cout << 1
void foo(int x) {
cout << x;
}
----------------
foo(1);
Recursion
• What will happen with the following?
void foo(int x) { foo(1): cout << 1, foo(2)
cout << x; foo(2): cout << 2, foo(3)
foo(3): cout << 3, foo(4)
foo(x+1);
…
} Somethings must stop it!!
----------------
foo(1); foo(10): Oh I reached 10, enough!! Let’s go back.
• A function calling itself is called recursion.
Recursion
• What will happen with the following?
Output:
1
void foo(int x) { 2
if (x == 10) foo(1): cout << 1, foo(2) 3
foo(2): cout << 2, foo(3) 4
return; foo(3): cout << 3, foo(4)
5
6
cout << x; … 7
foo(x+1); Somethings must stop it!! 8
9
}
---------------- foo(10): Oh I reached 10, enough!! Let’s go back.
foo(1);
• A function calling itself is called recursion.
Recursion
• What will happen with the following?
Output:
1
void foo(int x) { foo(1): cout << 1, foo(2) 2
foo(2): cout << 2, foo(3) 3
if (x == 10) 4
foo(3): cout << 3, foo(4)
return; …
5
6
cout << x; 7
foo(x+1); foo(9): cout << 9, foo(9) 8
9
cout << x; foo(10): Oh I reached 10, 9
} enough!! Let’s go back. 8
foo(9): cout << 9 7
---------------- 6
foo(8): cout << 8
foo(1); ..
5
4
foo(1): cout << 1 3
2
1
What is Recursion?
• Recursive call: A method call in which the method being called is the
same as the one making the call.
• Direct recursion: Recursion in which a method directly calls itself.
• Indirect recursion: Recursion in which a chain of two or more method
calls returns to the method that originated the chain.
• Tail recursion: The case in which a function contains only a single
recursive call and it is the last statement to be executed in the function.
Recursion
• You must be careful when using recursion.
• Recursive solutions are typically less efficient than iterative
solutions. Avoid them !!!
• Still, many problems lend themselves to simple, elegant, recursive
solutions.
• We must avoid making an infinite sequence of function calls.
Recursive Solutions
• A recursive solution calls itself
• Each recursive call solves an identical, smaller problem
• Test for base case enables recursive calls to stop
• Eventually one of smaller calls will be base case
Questions for Constructing the Recursive Solutions?
• How to define the problem in terms of a smaller problem of
same type?
• How does each recursive call diminish the size of the
problem?
• What instance of problem can serve as base case?
• As problem size diminishes, will you reach base case?
Recursion: General Format
if (some known condition) // base case
solution statement
else // general case
recursive function call
• Each successive recursive call should bring you closer to a situation
in which the answer is known.
• Each recursive algorithm must have at least one base case, as well
as the general case (recursive)
Recursion: General Format (Common)
if (some known condition) // base case
return base value (or void)
// general case
recursive function call
return general case value
• Each successive recursive call should bring you closer to a situation
in which the answer is known.
• Each recursive algorithm must have at least one base case, as well
as the general case (recursive)
Recursion: Factorial
• 3! = 3 × 2! = 3 × 2 × 1! = 3 × 2 × 1
• fact(3) = 3 * fact(2) = 3 * 2 * fact(1) = 3 * 2 * 1
int fact(int N) {
if (N == 0)
return 1;
return N*fact(N-1);
}
----------------
cout << fact(3);
Factorial: Step-by-Step
int fact(3) int fact(3)
if(3 == 1)(False) if(3 == 1)(False)
… …
return 3*fact(2); return 3*2;
int fact(2) int fact(2)
if(3 == 1)(False) if(3 == 1)(False)
… …
return 2*fact(1); return 2*1;
int fact(1)
if (1 == 1)(True)
return 1;
…
Fibonacci Numbers
• Sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
• F1 = 1, F2 = 1
• FN = FN - 1 + FN - 2
Fibonacci Numbers
Fibonacci Numbers: Recursion Performance
Exercise: Convert to iterative…
𝒏
Compute 𝑪𝒌
• How many ways to choose groups of size k out of n?
• For every element, either:
– take it in the current group and take 𝒌 − 𝟏 from the remaining 𝒏 − 𝟏, or
– ignore it, and take 𝒌 from the remaining 𝒏 − 𝟏
𝒏
Compute 𝑪𝒌
If there are multiple recursion calls, there might be multiple base
cases!!
𝒏
Compute 𝑪𝒌
Tower of Hanoi: Problem
• Problem statement
– Beginning with n disks on pole A and zero disks on poles B and C, solve
towers(n, source, destination, auxiliary) .
Tower of Hanoi: Two Disks
Src Aux Dst
Src Dst Aux
Src Dst Aux
Src Aux Dst
Aux Src Dst
Aux Dst Src
Tower of Hanoi: Generalize
What if 𝒏 = 𝟏?
Towers of Hanoi: Pseudocode
Base Case
General Case
Tower of Hanoi: Three Disks Tracing
30
Tower of Hanoi: C++ Code
Tail Recursion
• If the recursive call appears as the last step in the function, then it
can be converted to iterative.
• Is this tail recursion?
void foo(int x) {
cout << x;
foo(x+1);
}
----------------
foo(1);
Tail Recursion
• If the recursive call appears as the last step in the function, then it
can be converted to iterative.
• Is this tail recursion?
int fact(int N) {
if (N == 0)
return 1;
return N*fact(N-1);
}
----------------
cout << fact(3);
Tail Recursion
• If the recursive call appears as the last step in the function, then it
can be converted to iterative.
• Is this tail recursion?
Tail Recursion
• If the recursive call appears as the last step in the function, then it
can be converted to iterative.
• Is this tail recursion?
