Python Recursion: Types of Recursion in Python

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.

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 functionrecursive_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 fixesn_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.

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

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.