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