Recursion for Beginners 🙂
Tags: programming, beginners, tutorial, python
Published: 2022-10-04 17:48:59

<h1> What is Recursion ? </h1>

Recursion is the way of making a function call itself. The below diagram shows that the function func is calling itself in it's body:

```python
def func(): <--
              |
              | (recursive call)
              |
func() --------
``` 

_______
<h1> Working of a Recursive step </h1>
______
<h3> 1. Components of a recursive function </h3>

The condition that stops a recursive function to repeat endlessly is known as base condition.
  
   
```python
def func(a):    <------------
    if(a < 5):              |
        func(a+1)---------->| (recursive step)
    print(a)                |
func(0) -------------------> (here we are taking a as 0)
``` 
The above function print all numbers in range ( a to 5 ). The function stops executing as soon as the base condition is met. Below is the output . 

```python
5
4
3
2
1
0
``` 

If we remove the base condition it raises <mark style="background-color: #FFFF00"> RecursionError</mark>  . This happens because there is no restrictions on when the function should be called . Hence it is repeating the same function indefinitely. Check the output below :

```python
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
```
Okay, by now you must have grabbed the concept of base case and recursive step. Yay 😎

_________

<h3> 2. Recursive Tree </h3>

If you think that the first recursive function is ended instantly as the last function is ended, then you are wrong. 

What happens in recursion is that the first function calls the second function which in return calls the third function and so forth . A parent functions is ended only if all of it's children functions have ended. 

```python
main( ) <--- 
           | (returning to main() function)
func(0) <---
   ↓       |
func(1) <---
   ↓       |
func(2) <---
   ↓       |
func(3) <---
   ↓       |
func(4) ---> (returning to parent function)
```
The above diagram is known as <mark style = "background-color : #00ff00">Recursion Tree</mark>  . It is the best way to visualize the recursion.

_______

<h3> 3. Head Recursion vs Tail Recursion </h3>

In head recursion you perform your recursive calls first, and then you take the return value of the recursive call and calculate the result. While, in tail recursion you perform your calculations first, and then you execute the recursive call, passing the results of your current step to the next recursive step.

Below is the code for head recursion : 
```python
def headrec(n):
    if(n == 0):
        return
    else:
        headrec(n-1)
    print(n)
```
Below is the code for tail recursion : 
```python
def tailrec(n):
    if(n == 1):
        return
    else:
        print(n)
    tailrec(n-1)
```

__________

<h1> Examples </h1>
_________
<h3> 1. Calculate Sum of n Natural Numbers </h3>

```python
def recurSum(n):
    if n <= 1:
        return n
    return n + recurSum(n - 1)

print(recurSum(100))
```
The output below shows the sum of n(100) natural numbers

```python
5050
```

_________

<h1> Should I Use it or Not </h1>
____
|  Advantages                                                                 |Disadvantages                                                          |
|------|-----------------------------------------------------------------------|
|Recursion adds clarity and sometimes reduces the time needed to write code.|Recursive solution is always logical and it is very difficult to trace.|
|Recursion helps to break down the problem into easy small steps.           |It always needs an if condition.                                       |
|Reduce unnecessary calling of functions.                                   |Recursion uses more processor time.                                    |
|Reduce overall size of code.                                               |Can lead to stack overflow.                                            |
___________
Thanks for reading .🙂