Recursion
Recursion
What do you think the behaviour of these two
functions if they are called with 10?
void fun(int i){ void fun(int i){
if(i==0) if(i==0)
return; return;
fun(i-1); cout<<i<<'\n';
cout<<i<<'\n'; fun(i-1);
} }
Recursion
● Recursion is the process in which a function calls
itself.
● Recursion is the process of defining a problem
(or the solution to a problem) in terms of (a
simpler version of) itself.
● Stack plays an important rule with recursion to
keep track the function calls
Recursion
● To Write a recursive function, you need to think about two
things:
1. The recursion logic (The transition): How to get the answer of
the current problem from the answer(s) of simpler version(s)
of it
2. The base case(s): When this recursion will end
Recursion: Example 1
Write a recursive code to implement the power
function of integer base and power
base=2, exponent=3
power(2,3)=8
base=3, exponent=4
power(3,4)=81
Recursion: Example 1
1. The recursion logic (The transition):
If I have the answer of the same problem but in previous
version power(base, exponent-1), I can get the answer for the
current version power(base, exponent)
power(base, exponent) =base * power(base, exponent-1)
2^4 = 2 * 2^3
2. The base case:
When I get to the version where exponent=0, the answer
is 1
Recursion: Example 1
int power(int base, int exponent){
// base case
if(exponent==0) return 1;
// Transition
return base * power(base,
exponent-1);
}
Recursion: Example 2
Write a recursive code to calculate the n-th (zero
based) fibonacci number.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
n=0 → fib(0) = 0
n=3 → fib(3) = 2
n=6 → fib(6) = 8
Recursion: Example 2
1. The recursion logic (The transition):
If I have the answers of fib (same problem) for the previous
two versions (n-1&n-2), I can get the answer for the current
version (n)
fib(n)=fib(n-1)+fib(n-2)
2. The base case(s):
When I get to the version where n=0, the answer is 0
When I get to the version where n=1, the answer is 1
Recursion: Example 2
int fib(int n){
// base cases
if(n==0) return 0;
if(n==1) return 1;
// Transition
return fib(n-1)+fib(n-2);
}