What is Recursion in Python?

Recursion in Python helps solve complicated problems by breaking them down into smaller, similar problems, making the code cleaner and easier to understand and maintain. This blog will delve into what recursion is in Python as well as explore real-world use cases of recursion in Python.

Table of Contents:

• What is Recursion in Python?
• What are Recursive Functions?
• Types of Recursion in Python
• Applications of Recursion in Python
• Real-World Use Cases of Recursion in Python
• Difference Between Recursion and Iteration
• Conclusion

Check out this YouTube video to learn about Python:

What is Recursion in Python?

Recursion in Python is a programming method where a function calls itself, either directly or indirectly. It’s a powerful tool for solving complicated problems by breaking them into smaller, similar sub-problems. This approach simplifies code and leads to elegant solutions, especially for tasks with repetitive patterns.

Example of a Python program that calculates the factorial of a number using recursion:

def factorial(n):
    if n <= 1:
        return 1
    else:
        return n * factorial(n - 1)
# Input from the user
num = int(input("Enter a non-negative integer: "))
if num < 0:
    print("Factorial is not defined for negative numbers.")
else:
    result = factorial(num)
    print(f"The factorial of {num} is {result}")

Output:

Enter a non-negative integer: 4

The factorial of 4 is 24

To learn this latest programming language, sign up for Intellipaat’s trending Python Course and become proficient in it!

What are Recursive Functions?

A recursive function is a specific implementation of recursion. Instead of solving a complex problem directly, recursive functions break it down into smaller, more manageable instances of the same problem. 

Each time the function is called, it operates on a smaller or simpler part of the problem until it reaches a base case—a condition where the function returns a specific result without making any further recursive calls. 

Recursive functions are commonly used in various programming languages, including Python, to solve problems that exhibit repetitive or self-similar structures.

Types of Recursion in Python

Recursion can be categorized into two main types: direct recursion and indirect recursion. 

1. Direct Recursion:

Direct recursion occurs when a function calls itself directly. It can be categorized into four subtypes: tail recursion, head recursion, tree recursion, and nested recursion.

• Tail Recursion

This type of recursion is a type of direct recursion in which the recursive call is the last operation in the function. This allows the compiler or interpreter to optimize the recursion, as it doesn’t need to maintain a stack of function calls.

Code:

def factorial_tail(n, result=1):
    if n == 0:
        return result
    else:
        return factorial_tail(n - 1, n * result)
result = factorial_tail(5)
print(result)  

Output: 

120

• Head Recursion

Head recursion is the opposite of tail recursion. Here, the recursive call is the first operation performed in a function. This type is less common and doesn’t benefit from the same optimization as tail recursion.

Code:

def factorial_head(n):
    if n == 0:
        return 1
    else:
        return n * factorial_head(n - 1)
result = factorial_head(5)
print(result)  

Output: 

120

• Tree Recursion

Tree recursion occurs when a function makes multiple recursive calls, branching into a tree-like structure of recursive calls. This is often seen in problems related to trees or hierarchical structures.

Code:

def fibonacci_tree(n):
    if n <= 1:
        return n
    else:
        return fibonacci_tree(n - 1) + fibonacci_tree(n - 2)
result = fibonacci_tree(6)
print(result)  

Output:

8

• Nested Recursion

Nested recursion involves a function calling itself with a recursive call as one of its arguments.

Code:

def nested_recursion(n):
    if n <= 0:
        return 1
    else:
        return nested_recursion(n - nested_recursion(n - 1))
result = nested_recursion(3)
print(result)  

Output: 

1

2. Indirect Recursion:

Indirect recursion occurs when two or more functions call each other in a circular manner. 

Code:

def is_even(n):
  if n == 0:
    return True
  else:
    return is_odd(n - 1)
def is_odd(n):
  if n == 0:
    return False
  else:
    return is_even(n - 1)
print(is_even(10))
print(is_odd(10)) 

Output:

True

False

Want to know about the real-world uses of Python? Read our detailed blog on Python Applications now.

Applications of Recursion in Python

Recursion is a powerful programming technique in Python that finds applications in various problem-solving scenarios. Some common applications of recursion in Python include:

• Mathematical Calculations:
  • Calculating factorials
  • Computing Fibonacci numbers
  • Solving mathematical series, such as the sum of the first N natural numbers

• Data Structures:

• Traversing and manipulating tree structures (e.g., binary trees, AVL trees)
• Performing operations on graphs (e.g., depth-first search, finding connected components)
• Implementing recursive data structures like linked lists

• File System Operations:

• Navigating and searching directories and files in a directory tree
• Recursively copying, moving, or deleting files and folders

• Combinatorial Problems:
  • Solving problems involving combinations and permutations, such as generating all possible subsets or permutations of a set of elements
  • Solving the Tower of Hanoi problem

• Backtracking Algorithms:
  • Solving problems that require exploration of all possible solutions, like the N-Queens problem or Sudoku puzzles
  • Solving maze traversal problems

• Sorting Algorithms:
  • Some sorting algorithms, like quicksort and mergesort, use recursion as part of their divide-and-conquer strategy.

• AI and Machine Learning:

Implementing recursive algorithms in AI and machine learning applications, such as decision trees and neural network architectures, is crucial for enhancing their functionality and efficiency.

Learn the basics of Python from Python Fundamentals tutorial.

Real-World Use Cases of Recursion in Python

Here are a few real-world use cases of recursion in Python:

• Directory Structure and File Size Calculation

Problem Statement: You are tasked with calculating the total size of a directory and all its subdirectories. Given a directory path, write a Python program that recursively traverses the directory structure, sums up the sizes of all files, and reports the total size in bytes.

import os
def calculate_directory_size(path):
    if os.path.isfile(path):
        return os.path.getsize(path)
    total_size = 0
    for child in os.listdir(path):
        child_path = os.path.join(path, child)
        if os.path.isdir(child_path):
            total_size += calculate_directory_size(child_path)
        elif os.path.isfile(child_path):
            total_size += os.path.getsize(child_path)
    return total_size
directory_path = "/path/to/directory"
size = calculate_directory_size(directory_path)
print(f"Total size of {directory_path}: {size} bytes")

• Towers of Hanoi

Problem Statement: You are given three pegs (A, B, and C) and a stack of n disks of different sizes, initially arranged on peg A in decreasing order of size (largest at the bottom). The task is to move the entire stack to peg C, obeying the following rules:

• Only one disk can be moved at a time.
• A disk can only be placed on top of a larger disk or an empty peg (never on top of a smaller disk).

Write a Python program using recursion to solve the Towers of Hanoi puzzle and print the steps required to move the entire stack from peg A to peg C.

def towers_of_hanoi(n, source, auxiliary, target):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    towers_of_hanoi(n-1, source, target, auxiliary)
    print(f"Move disk {n} from {source} to {target}")
    towers_of_hanoi(n-1, auxiliary, source, target)
n_disks = 3  # Adjust the number of disks as needed
towers_of_hanoi(n_disks, 'A', 'B', 'C')

Prepare yourself for the industry by going through Python Interview Questions and Answers now!

Difference Between Recursion and Iteration

Recursion and iteration are two fundamental concepts in programming for solving repetitive tasks. Below is a comparison of recursion and iteration:

Conclusion

Recursion in Python is a powerful technique that involves defining a function in terms of itself. We’ve explored its fundamentals, from understanding recursive functions to diving into various types of recursion. 

Through real-world examples and applications, we have seen how recursion can efficiently solve complex problems. This blog on recursion highlights how it can be a valuable tool for Python programmers, offering smart solutions to a wide range of complex problems.