Recursion
What is Recursion
Repeated application of a recursive procedure or definition.
When you call a method within itself, we call such a call a Recursive Call
Example Problems
Simple Recurision Factorial Problem
#include<iostream>
int Factorial(int n)
{
if (n == 0)
{
return 1; // Exit Condition
}
return n*Factorial(n-1);
}
int main()
{
int n;
std::cout << "Input a number n: ";
std::cin >> n;
int result = Factorial(n);
std::cout << n << "! = " << result << std::endl;
}
Output:
If n = 5
Input a number n: 5
5! = 120
Another Example
#include<iostream>
int Factorial(int n)
{
std::cout << "I am Calculating F( " << n << ")\n";
if (n == 0)
{
return 1;
}
int F = n*Factorial(n-1);
std::cout << "Done ! F(" << n << ") = " << F << "\n";
return F;
}
int main()
{
int n;
std::cout << "Input a number n: ";
std::cin >> n;
int result = Factorial(n);
std::cout << result << std::endl;
// std::cout << n << "! = " << result << std::endl;
}
If we make n = 5 again.
Output
Input a number n: 5
I am Calculating F( 5)
I am Calculating F( 4)
I am Calculating F( 3)
I am Calculating F( 2)
I am Calculating F( 1)
I am Calculating F( 0)
Done ! F(1) = 1
Done ! F(2) = 2
Done ! F(3) = 6
Done ! F(4) = 24
Done ! F(5) = 120
120
Why Recursion isnt always the best
Finding Fibonacci Sequence
Iterative Example
#include<iostream>
int Fib(int n){
if (n <= 1)
{
return n;
}
int F1, F2, F;
F1 = 0;
F2 = 1;
for (int i = 2; i <= n; i++)
{
F = F1 + F2;
F1 = F2;
F2 = F;
}
return F;
}
int main()
{
int n;
std::cout << "Give me an n: " ;
std::cin >> n;
int result = Fib(n);
std::cout << result << std::endl;
}
Output:
Give me an n: 40
102334155
Recursive Way
#include<iostream>
int Fib(int n){
if (n <= 1)
{
return n;
}
return Fib(n-1) + Fib(n-2);
}
int main()
{
int n;
std::cout << "Give me an n: " ;
std::cin >> n;
int result = Fib(n);
std::cout << result << std::endl;
}
Output
Give me an n: 6
8
(base) Devins-MBP-2:Recursion devinpowers$ ./a.out
Give me an n: 40
102334155
Both Examples worked, but the recursive method took much longer time to execute!!! Why? because the iterative example only calculated F(n) once, while the recursive example calculated F(n) multiple times. You can see the multiple times it calculated F(n) in the recursive tree below.
Therefore it is way faster using iterative to calculate Fibonacci Sequence!
Time and Space Complexity Analysis of Recursive Programs - Using Factorial
Time Complexity: is the measurement of the time taken as a program grows with input
Space Complexity: is the measurement of how much the space or memory consumed as a program grows with input
When we try to analyize time complexity of a program we make an assumption that each simple operation costs us one unit of time (e.g. comparison, multiplication, addition, etc)
Time Complexity of Recursion - Fibonacci Sequence
Fibonacci Sequence - Recursion with Memoization
- Technique to improve the performace of a Recursive Program
Lets do something to avoid the re-calculation of the same state or the same value again and again
Fibonacci Sequence with Memoization
#include<iostream>
// Global Only one copy is created
int F[51];
int Fib(int n){
if (n <= 1)
{
return n;
}
if(F[n] != -1)
{
return F[n];
}
F[n] = Fib(n-1) + Fib(n-2);
return F[n];
}
int main()
{
for (int i = 0; i < 51; i++)
{
F[i] = -1;
}
int n;
std::cout << "Give me an n: " ;
std::cin >> n;
int result = Fib(n);
std::cout << result << std::endl;
}
Output
With n = 40
Give me an n: 40
102334155
- It took way faster for the program to execute!!
So recursion with memoization in this particular example is not as efficient as an iterative implementation in terms of memory but it is as good as an iterative implementation in terms of time.
Reduces the time complexity!