# 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)

### 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!