4 6 Recursion Explained

Key Concepts

Recursion in Python is a technique where a function calls itself to solve a problem. The key concepts include:

• Base Case
• Recursive Case
• Stack Overflow
• Practical Applications

1. Base Case

The base case is the condition that stops the recursion. It is essential to have a base case to prevent infinite recursion.

Example:

def factorial(n):
    if n == 0:
        return 1  # Base case
    else:
        return n * factorial(n - 1)  # Recursive case

print(factorial(5))  # Output: 120
    

2. Recursive Case

The recursive case is where the function calls itself with a modified argument, moving closer to the base case.

Example:

def fibonacci(n):
    if n <= 1:
        return n  # Base case
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # Recursive case

print(fibonacci(6))  # Output: 8
    

3. Stack Overflow

Stack overflow occurs when the recursion depth exceeds the available memory, leading to a crash. It is crucial to ensure that the base case is reachable.

Example of a problematic recursive function:

def infinite_recursion(n):
    return infinite_recursion(n)  # No base case, leads to stack overflow

# Uncommenting the next line will cause a stack overflow
# infinite_recursion(1)
    

4. Practical Applications

Recursion is useful for solving problems that can be broken down into smaller, similar subproblems. Examples include tree traversal, sorting algorithms, and mathematical computations.

Example: Tree traversal using recursion

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)

# Creating a simple binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

inorder_traversal(root)  # Output: 4 2 5 1 3
    

Putting It All Together

By understanding and using recursion effectively, you can solve complex problems in a structured and elegant manner. Ensure that your recursive functions have a clear base case to avoid stack overflow and make your code more robust.

Example: Recursive function to reverse a string

def reverse_string(s):
    if len(s) == 0:
        return s  # Base case
    else:
        return reverse_string(s[1:]) + s[0]  # Recursive case

print(reverse_string("hello"))  # Output: olleh