advanced

Recursive Functions

Q: What happens if I forget the base case?

Infinite recursion until Python hits the recursion limit (usually 1000 calls) and raises RecursionError.

Q: Why use recursion instead of a loop?

Recursion is clearer for naturally recursive problems (trees, divide-and-conquer). For simple counting, loops are more efficient.

Q: What's the call stack?

Python remembers each recursive call in memory. Each call is added to the stack, then removed when it returns.

Q: Can recursion run out of memory?

Yes! Deep recursion can cause stack overflow. Python limits recursion depth to prevent this.

Learn recursion by creating functions that call themselves.

Recursion is when a function calls itself to solve smaller instances of the same problem. It is powerful for problems that can be broken down into similar subproblems.

📚 Concepts & Theory

Recursion is a programming technique where a function calls itself to solve a problem by breaking it into smaller, similar subproblems.

Basic Recursion Pattern:

def recursive_function(parameter):

    # Base case: stop condition

    if base_condition:

        return base_value

    

    # Recursive case: call itself with smaller problem

    return recursive_function(smaller_parameter)

Classic Example - Factorial:

def factorial(n):

    # Base case

    if n == 0 or n == 1:

        return 1

    

    # Recursive case

    return n * factorial(n - 1)

# factorial(5) = 5 * factorial(4)

#              = 5 * 4 * factorial(3)

#              = 5 * 4 * 3 * factorial(2)

#              = 5 * 4 * 3 * 2 * factorial(1)

#              = 5 * 4 * 3 * 2 * 1

#              = 120

Essential Components:

1. Base Case (Stopping Condition):
Prevents infinite recursion, provides final answer:

if n == 0:

    return 1  # Must return, not recurse

2. Recursive Case:
Calls itself with a simpler/smaller problem:

return n * factorial(n - 1)  # n-1 is smaller

3. Progress Toward Base Case:
Each call must get closer to the base case:

factorial(5) → factorial(4) → factorial(3) → ... → factorial(1)

More Examples:

Countdown:

def countdown(n):

    if n <= 0:

        print("Done!")

        return

    print(n)

    countdown(n - 1)

countdown(5)  # Prints 5, 4, 3, 2, 1, Done!

Sum of List:

def sum_list(numbers):

    if not numbers:  # Empty list

        return 0

    return numbers[0] + sum_list(numbers[1:])

sum_list([1, 2, 3, 4, 5])  # 15

Fibonacci:

def fibonacci(n):

    if n <= 1:

        return n

    return fibonacci(n-1) + fibonacci(n-2)

# fibonacci(5) = 5

String Reversal:

def reverse(text):

    if len(text) <= 1:

        return text

    return reverse(text[1:]) + text[0]

reverse("hello")  # "olleh"

Recursion vs Iteration:

Recursive:

def sum_recursive(n):

    if n == 0:

        return 0

    return n + sum_recursive(n - 1)

Iterative:

def sum_iterative(n):

    total = 0

    for i in range(n + 1):

        total += i

    return total

When to Use Recursion:
✅ Tree/graph traversal
✅ Divide and conquer algorithms
✅ Problems with recursive structure (factorials, Fibonacci)
✅ Backtracking problems

When NOT to Use:
❌ Simple iterations (use loops)
❌ Performance critical code (recursion has overhead)
❌ Very deep recursion (stack overflow risk)

Python Recursion Limit:

import sys

print(sys.getrecursionlimit())  # Usually 1000

# Can increase (carefully!)

sys.setrecursionlimit(2000)

Common Pitfalls:

# ❌ No base case - infinite recursion!

def bad_function(n):

    return bad_function(n - 1)

# ❌ Never reaches base case

def bad_countdown(n):

    if n == 0:

        return

    print(n)

    bad_countdown(n + 1)  # Gets larger, not smaller!

# ✅ Proper recursion

def good_countdown(n):

    if n == 0:

        return

    print(n)

    good_countdown(n - 1)  # Gets smaller

🎯 Your Challenge

Create a recursive function countdown(n) that prints numbers from n down to 1, then prints "Blast off!"

📝 Starter Code

Python

def countdown(n):
    pass

Start with the base case: if n <= 0
In base case, print Blast off! and return
In recursive case, print the current number
Then call countdown(n - 1) for the next smaller number
Make sure each call gets closer to the base case

Solution

Python

def countdown(n):
    if n <= 0:
        print("Blast off!")
        return
    print(n)
    countdown(n - 1)

Explanation

This recursive function demonstrates the classic recursion pattern. The base case (n <= 0) stops the recursion by printing "Blast off!" and returning without further calls. The recursive case prints the current number n, then calls countdown(n - 1) with a smaller value, progressing toward the base case. When countdown(5) is called, it prints 5, calls countdown(4), which prints 4, calls countdown(3), and so on until countdown(0) triggers the base case. The recursion "unwinds" back up the call stack. This is cleaner than iteration for problems with natural recursive structure.

⚠️ Common Mistakes to Avoid

Forgetting the base case (causes infinite recursion/stack overflow)
Base case that never triggers (wrong condition)
Not making progress toward base case (n+1 instead of n-1)
Forgetting to return in base case
Printing in wrong order (before vs after recursive call matters)

❓ Frequently Asked Questions

Infinite recursion until Python hits the recursion limit (usually 1000 calls) and raises RecursionError.

Recursion is clearer for naturally recursive problems (trees, divide-and-conquer). For simple counting, loops are more efficient.

Python remembers each recursive call in memory. Each call is added to the stack, then removed when it returns.

Yes! Deep recursion can cause stack overflow. Python limits recursion depth to prevent this.

📚 Concepts & Theory

🎯 Your Challenge

📝 Starter Code

Solution

Explanation

⚠️ Common Mistakes to Avoid

❓ Frequently Asked Questions

🔗 Related Exercises

While Loops

Higher-Order Functions

Lambda Functions

Variable Scope