11

Oct# Recursion in Python: A Detailed Explanation

## Recursion in Python

**Recursion in Python **is a strategy where a function calls itself in order to solve complex problems. It is a popular mathematics and computer concept that lets you loop through data and get a result. By **Recursion**, you can solve bigger and more complicated problems by breaking them down into smaller, similar problems, making the code cleaner and easier to understand and maintain.

Here in the **Python tutorial**, we will learn key concepts about **what ****Recursion in Python is **and** Why we use Recursion**, including its **types of Recursion in Python**,** basic examples of Recursion**, **real-world problems**, **advantages & disadvantages**, and many more.

## What is Recursion in Python?

**Recursion in Python** is a programming concept where a function calls itself directly or indirectly. It’s a robust approach for solving complex problems by dividing them into smaller and similar sub-problems such as tree traversal, searching, and sorting. Let's understand this by some points;

- It occurs when a
**function in Python**calls itself to solve smaller instances of the same problem. - There is a base case, which is a condition that stops the recursion to avoid infinite loops and potential crashes.
- Each recursive call integrates a new layer to the call stack that can cause high memory usage if not managed carefully.
- Python does not improve recursive calls. Hence, deep recursion can result in stack overflows.

Read More: Functions in Python-A Comprehensive Guide |

## Why do we need Recursion?

We need** recursion** to simplify and efficiently solve complex problems that can be broken down into smaller, similar sub-problems. Let's understand its importance in the points below.

- Divide complex problems into smaller, more manageable problems.
- It is highly recommended for problems like
**tree traversal**,**factorials**, and the**Tower of Hanoi**. - Provide more concise and readable code.
- Uses the call stack to manage operations, reducing the need for additional structures like
**stacks**or**queues**. - Essential in algorithms like
**quicksort**and**mergesort**, where problems are split into smaller pieces to solve recursively.

### Syntax

### Examples of Recursive Functions in Python

#### 1. Create a Python Program to find the factorial of a positive integer number.

```
# Create a program to find the factorial of a positive integer number
# Recursive function
def recursive_factorial(n):
if n == 1:
return n
else:
return n * recursive_factorial(n-1)
# user input
num = 7
# find if the input is valid or not
if num < 0:
print("Invalid input ! Please enter a positive number.")
elif num == 0:
print("The factorial of number 0 is 1")
else:
print("The factorial of number", num, "=", recursive_factorial(num))
```

#### Output

```
Factorial of number 7 = 5040
```

#### Explanation

- The function
**recursive_factorial(n)**executing itself finds the factorial of a number with**n-1**until it reaches the base case where**n = 1**. - In the
**if statement**num is less than 0, it prints an error; if num is equal to 0, it prints that the factorial is 1. - For positive integer num, the factorial is calculated by the multiplication of n with the recursive_factorial(
**n-1)**until it reaches the base case. - After completing the operation, it prints the result.

#### 2. Create a Python Program to find the Fibonacci Sequence

```
# Program to print the fibonacci series upto n_terms
# Recursive function
def recursive_fibonacci(n):
if n <= 1:
return n
else:
return(recursive_fibonacci(n-1) + recursive_fibonacci(n-2))
n_terms = 10
# check if the number of terms is valid
if n_terms <= 0:
print("Invalid input ! Please input a positive value")
else:
print("Fibonacci series:")
for i in range(n_terms):
print(recursive_fibonacci(i))
```

#### Output

```
Fibonacci series:
0
1
1
2
3
5
8
13
21
34
```

#### Explanation

- The function
**recursive_fibonacci(n)**computes the nth**Fibonacci**number by adding the values of the preceding two Fibonacci numbers**(n-1 and n-2)**, with base cases returning n directly when n equals**0**or**1**. - The program fixes
**n_terms**to**10**, meaning it will print the first**10**numbers of the Fibonacci series. - It checks to see if
**n_terms**is positive; if it is not, it outputs an error message; otherwise, it generates the series. - The program iterates from
**0**to**n_terms-1**, executing**recursive_fibonacci(i)**for each term and printing the Fibonacci numbers consecutively.

Read More |

Top 10 Python Developer Required Skills You Must Know in 2024 |

Python Career Guide: Why is It Important in 2024? |

Python Developer Roadmap: How to Be a Python Developer? |

**Recursion** can be classified based on how the recursive function is organized. Here are the common forms of **recursion in Python:**

### 1. Tail Recursion

**Tail Recursion** is a unique type of recursion where the recursive call is the last operation in the function. There is no requirement to hold any previous state after the recursive call, allowing for optimization in some languages. However, Python does not optimize for tail recursion.

#### Example

```
def tail_recursive_factorial(n, accumulator=1):
# Base case: if n is 0 or 1, return the accumulator
if n == 0 or n == 1:
return accumulator
# Recursive case: multiply n by the accumulator and pass it to the next call
else:
return tail_recursive_factorial(n-1, n * accumulator)
# Example usage
result = tail_recursive_factorial(5)
print(result)
```

#### Output

```
120
```

#### Explanation

- The function
**tail_recursive_factorial(n, accumulator=1)**computes the factorial of n using tail recursion, with the result accumulated after each recursive iteration to avoid creating a call stack. - In the basic case, if
**n**is**0**or**1,**the function returns the accumulated result**(accumulator)**, which contains the calculated factorial number. - In the recursive case, the function multiplies
**n**by the accumulator before calling itself with**n-1**, passing the updated accumulator until it reaches the base case. - In the example,
**tail_recursive_factorial(5)**computes**5!**by progressively multiplying and passing the result until the final value**120**is returned and printed.

### 2. Head Recursion

**Head recursion** occurs when the recursive call is made before any other operations in the function. This means that the function starts processing the recursive calls before handling any other work in the current function.

#### Example

```
def head_recursive_print(n):
# Base case: if n is less than or equal to 0, do nothing
if n > 0:
# Recursive case: call the function with n-1 first
head_recursive_print(n-1)
# After the recursive call, print the current number
print(n)
# Example usage
head_recursive_print(5)
```

#### Output

```
1
2
3
4
5
```

#### Explanation

- The function
**head_recursive_print(n)**is designed to print numbers from**1**to**n**using head recursion, where the recursive call is made before any other action. **Base Case:**If**n**is less than or equal to**0**, the function does nothing, effectively stopping further recursion.**Recursive Case:**The function first calls itself with**n-1**, which continues to reduce**n**until it reaches the base case.- After reaching the base case and beginning to return from each recursive call, the function prints the current value of
**n**, resulting in numbers being printed in ascending order from**1**to**n**.

### 3. Indirect Recursion

**Indirect Recursion** happens when a function calls another function, and then that second function calls the first function back. It makes a loop or a cycle between two functions and more than two functions. With indirect recursion, multiple functions are involved, each relying on the other to continue the process.

#### Example

```
def function_a(n):
if n > 0:
print(f"function_a: {n}")
function_b(n-1)
def function_b(n):
if n > 0:
print(f"function_b: {n}")
function_a(n-1)
# Example usage
function_a(3)
```

#### Output

```
function_a: 3
function_b: 2
function_a: 1
```

#### Explanation

- function_a(3) is called, which prints "function_a: 3" and then invokes function_b(2).
- function_b(2) executes, prints "function_b: 2", and calls function_a(1).
- function_a(1) runs next, prints "function_a: 1", and then calls function_b(0), which doesn't print anything and terminates because n is not greater than 0.
- The final output sequence is "function_a: 3", "function_b: 2", "function_a: 1", showing the alternating calls between function_a and function_b until the recursion ends.

### Tree Recursion

In this recursion, the function makes multiple recursive calls at each step, leading to a tree-like structure of calls.

#### Example

```
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
# Example usage
result = fibonacci(5)
print(result)
```

#### Output

```
5
```

#### Explanation

In this example,

- The
**fibonacci(n)**function uses recursion to compute the nth Fibonacci number;**fibonacci(0)**returns**0**,**fibonacci(1)**returns**1**, and for any**n > 1,**it returns the sum of the two preceding Fibonacci numbers. - When
**fibonacci(5)**is invoked, it recursively calculates**fibonacci(4)**and**fibonacci(3)**, which result in more recursive calls. - This method continues until the basic cases
**(fibonacci(0) and fibonacci(1))**are achieved, which are then utilized to compute the final result. - The end result is 5, which is written as the fifth number in the Fibonacci series.

### 5. Nested Recursion

In nested recursion, the recursive call is made within the parameters of another recursive call.

#### Example

```
def nested_recursion(n):
if n > 100:
return n - 10
else:
return nested_recursion(nested_recursion(n + 11))
# Example usage
result = nested_recursion(95)
print(result)
```

#### Output

```
91
```

#### Explanation

- In the base case, if
**n**is more than**100**, the function returns n - 10, which ends the recursion for that branch. - In the recursive situation, if n is
**100**or**less**, the function calls itself with**n + 11**, and the result is utilized as the input for the next recursive call to**nested_recursion**. - For
**nested_recursion(95)**, the code first runs**nested_recursion(106)**(since 95 + 11 = 106). Since 106 is more than 100, it returns**96 (106 - 10)**. - The outer call calls
**nested_recursion(96)**with this result**(96)**.

Read More |

Fibonacci Series in Python |

Factorial Calculator in Python |

If Else Statement In Python |

Real-World Problems Solved Using Recursion

There are several real-world problems solved by using Recursion that are depicted below:

### 1. Quick Sort

We use recursion to sort an array using the quick sort algorithm.

#### Example

```
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# Example usage:
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print(f"Sorted array: {sorted_arr}")
```

#### Output

```
Sorted array: [1, 1, 2, 3, 6, 8, 10]
```

#### Explanation

- In the basic case, if the array
**arr**has only**one**or**zero**members, it is already sorted and returned. - In the
**pivot portion**, the function chooses the**middle element of arr**as the pivot, dividing the array into three sections:**elements less than the pivot**,**elements equal to the pivot**, and**elements more than the pivot.** - The function recursively sorts the
**left**and**right**partitions and then combines them with the**middle**to produce the final sorted array, which is printed.

### 2. Towers of Hanoi

Move a set of disks from one rod to another, following specific rules (only one disk can be moved at a time, and no disk may be placed on top of a smaller disk).

#### Example

```
def towers_of_hanoi(n, source, target, auxiliary):
if n == 1:
print(f"Move disk 1 from {source} to {target}")
return
towers_of_hanoi(n-1, source, auxiliary, target)
print(f"Move disk {n} from {source} to {target}")
towers_of_hanoi(n-1, auxiliary, target, source)
# Example usage:
towers_of_hanoi(3, 'A', 'C', 'B')
```

#### Output

```
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
```

#### Explanation

- In the base scenario,
**if n == 1**, the method publishes the move for the smallest disk**(disk 1)**from the source to the target peg. This is the easiest execution, as only one disk needs to be relocated. - For
**n > 1**, the function begins by recursively moving the top**n-1**disks from the source peg to the**auxiliary peg**, utilizing the**target peg**as an intermediate. - After shifting
**n-1**disks to the**auxiliary peg**, the function outputs the**nth**disk's migration from the**source**to the**target peg**. - Finally, the function recursively moves the
**n-1 disks**from the**auxiliary peg**to**the target peg**, using the**source peg**as an intermediary.

## Advantages of Recursion in Python

Recursion is a powerful concept in programming, including Python, with several advantages that make it a valuable tool for solving certain types of problems. Here are some key advantages;

## Disadvantages of Recursion in Python

While recursion offers elegance, it comes with its own set of disadvantages.

- Stack Overflow Risk
- Performance Overheads
- High Memory Usage
- Debugging Difficulty
- Readability Problem

##### Summary

**Recursion in Python** is a significant and resourceful approach that simplifies complex problems by breaking them into smaller ones. However, **recursion** can help write cleaner and more concise code. Learning the types of recursion and their real-world problem-solving abilities helps developers write effective **Python code**. This was all about the **Recursion Python**; if you want to learn each concept widely, then consider enrolling in a **Python Certification Course.**

## FAQs

### Q1. Where is recursion used?

- Mathematical Computations
- Data Structures
- Divide and Conquer Algorithms
- Backtracking Algorithms

### Q2. What is Factorial Recursion in Python?

**Factorial recursion in Python**is a function that calls itself to calculate the factorial of a number by multiplying the number by the factorial of the number minus one, until it reaches a base case of 1.