☰ Java JavaScript Python C# C C++ Go Kotlin PHP Swift R Ruby TypeScript Scala SQL Perl rust VisualBasic Matlab Julia

Python Functions → Recursion

Python Functions

Recursion

Recursion in Python

Recursion, in the context of programming, is a powerful technique where a function calls itself within its own definition. This allows you to solve problems by breaking them down into smaller, self-similar subproblems. Each recursive call operates on a smaller version of the original problem until a base case is reached, stopping the recursion and returning a value back up the call stack. Think of it like a set of Russian nesting dolls: you open one to reveal a smaller version, and you continue until you reach the smallest doll.

Key Components of a Recursive Function

Base Case: This is the condition that stops the recursion. Without a base case, the function would call itself indefinitely, leading to a `RecursionError` (stack overflow). The base case defines the simplest version of the problem that can be solved directly. Recursive Step: This is where the function calls itself with a modified input, moving closer to the base case. The input should be simpler or smaller than the original input in each recursive call.

1. Factorial Calculation

The factorial of a non-negative integer n (denoted by n!) is the product of all positive integers less than or equal to n. For example, 5! = 5 * 4 * 3 * 2 * 1 = 120.
Basic Recursion example in Python def factorial(n): """Calculates the factorial of a non-negative integer using recursion.""" if n == 0: # Base case: factorial of 0 is 1 return 1 elif n < 0: # Handle negative input (optional) return "Factorial is not defined for negative numbers" else: return n * factorial(n - 1) # Recursive step print(factorial(5)) print(factorial(0)) print(factorial(-3))

Output

120 1 Factorial is not defined for negative numbers
In this example: ⮞ The base case is `n == 0`. ⮞ The recursive step is `n * factorial(n - 1)`. The function calls itself with a smaller input (`n - 1`) until it reaches the base case.

2. Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1.
Python Fibonacci Sequence example def fibonacci(n): """Calculates the nth Fibonacci number using recursion.""" if n <= 0: # Base case: 0th Fibonacci number is 0 return 0 elif n == 1: # Base case: 1st Fibonacci number is 1 return 1 else: return fibonacci(n - 1) + fibonacci(n - 2) # Recursive step print(fibonacci(6)) # Output: 8 (0, 1, 1, 2, 3, 5, 8)

Output

8
Here, we have two base cases (`n <= 0` and `n == 1`) and the recursive step combines the results of two previous Fibonacci numbers.

3. Tower of Hanoi

This classic puzzle involves moving a stack of disks of different sizes from one rod to another, using a third rod as a temporary holder, with the rule that a larger disk cannot be placed on top of a smaller disk.
Tower of Hanoi example in Python def tower_of_hanoi(n, source, destination, auxiliary): """Solves the Tower of Hanoi puzzle using recursion.""" if n == 1: # Base case: move the single disk directly print(f"Move disk 1 from {source} to {destination}") return else: tower_of_hanoi(n - 1, source, auxiliary, destination) # Move n-1 disks to auxiliary print(f"Move disk {n} from {source} to {destination}") # Move the largest disk tower_of_hanoi(n - 1, auxiliary, destination, source) # Move n-1 disks from auxiliary to destination tower_of_hanoi(3, 'A', 'C', 'B') # Output shows the steps to move 3 disks.

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
This example demonstrates a more complex recursive solution where the recursive calls are nested to solve a subproblem before moving to the next step.

Advantages of Recursion

Elegance and Readability: Recursive solutions can be more concise and easier to understand for problems that have a naturally recursive structure. Code Reusability: The same function is used to solve different subproblems.

Disadvantages of Recursion

Stack Overflow: Deep recursion can lead to stack overflow errors if the call stack exceeds its limit. Performance Overhead: Recursive calls can have higher overhead compared to iterative solutions due to function call management. Debugging Complexity: Debugging recursive functions can be more challenging.

When to Use Recursion

Recursion is best suited for problems that can be naturally broken down into smaller, self-similar subproblems. However, for very deep recursion or performance-critical applications, iterative solutions might be more efficient. Consider the trade-offs between readability and performance when choosing between recursive and iterative approaches.

Tutorials