Recursion : Python
Tags: python, programming, coding
Published: 2024-05-30 18:45:03



## Recursion

- Recursion is a programming technique where a function calls itself in order to solve a problem. 
- The recursive approach breaks a problem down into smaller, more manageable sub-problems of the same type.

### Components of Recursion:


1. **Base Case:**

   - The condition under which the recursion terminates.
   - It prevents infinite recursion by providing a simple, non-recursive solution to the smallest instance of the problem.
   
2. **Recursive Case:**
   - The part of the function where the function calls itself with a modified argument, gradually approaching the base case.

### Types of Recursion:

1. **Direct Recursion:**
   - A function calls itself directly.
   
2. **Indirect Recursion:**
   - A function calls another function, which in turn calls the original function.

### Example (Direct Recursion)

**Factorial Function:**


```python
def factorial(number):
    # base case
    if number == 1 or number == 0:
        return 1
    else:
        # Recursive case
        return number*factorial(number-1)
```

**Factorial of 5**


```python
fact = factorial(5)
print(f"factorial of 5 is : {fact}")
```

    factorial of 5 is : 120
    

- Here, `factorial(5)` calls `factorial(4)`, which calls `factorial(3)`, and so on, until it reaches `factorial(1)`.

### Example (Indirect Recursion)


```python
# variable to count how many times function called
function_call_count = 0

def functionA():
    # Telling function's local space that i am using global variable.
    global function_call_count 
    
    # Counting function call
    function_call_count += 1
    print("Printing from functionA().")
    
    # Base case to break the function call otherwise it will go infinitely calling functions.
    if function_call_count == 5:
        return
    
    # function call
    functionB()
    
def functionB():
    print("Printing from functionB().")
    
    # Function call
    functionA()

```


```python
# Calling functionA()
functionA()
```

    Printing from functionA().
    Printing from functionB().
    Printing from functionA().
    Printing from functionB().
    Printing from functionA().
    Printing from functionB().
    Printing from functionA().
    Printing from functionB().
    Printing from functionA().
    

### Advantages of Recursion:

- Simplifies the code for problems that can naturally be divided into similar sub-problems, like tree traversals, and certain mathematical computations (e.g., Fibonacci sequence).
- Provides a clear and straightforward approach to solve problems like backtracking and divide-and-conquer algorithms.


### Disadvantages of Recursion:

- Can lead to high memory usage due to the depth of the call stack, especially if the recursion depth is large.
- May result in slower performance compared to iterative solutions because of the overhead of multiple function calls.
- Risk of stack overflow if the base case is not properly defined or if the problem size is too large.

## Tail Recursion:

- A special form of recursion where the recursive call is the last operation in the function.

- Tail recursion can be optimized by the compiler to avoid increasing the call stack, converting the recursion into iteration internally.


## Example


```python
def tail_recursive_factorial(number, result = 1):
    if number == 1 or number == 0:
        return result
    
    # Recursive case (only recursive case)
    return tail_recursive_factorial(number-1, result*number)
```


```python
%%time
tail_recursive_factorial(5)
```

    CPU times: total: 0 ns
    Wall time: 0 ns
    




    120


##### _Most Important Python Does not optimize tail recursion. Some languages does not optimizes the tail recursion, and python is one of them._

## Conclusion

- Recursion is a powerful tool in programming, enabling elegant solutions for complex problems by breaking them down into simpler sub-problems. 
- However, it requires careful implementation to manage memory and performance effectively.