Python Recursion: Functions Calling Themselves

Recursion is a common mathematical and programming concept. It means that a function calls itself. This has the benefit of meaning that you can loop through data to reach a result.

1. What is Recursion?

A recursive function is a function that calls itself in its own definition.

def tri_recursion(k):
  if(k > 0):
    result = k + tri_recursion(k - 1)
    print(result)
  else:
    result = 0
  return result

print("\n\nRecursion Example Results")
tri_recursion(6)

2. The Base Case

Every recursive function must have a base case. The base case is the condition that stops the recursion. Without it, the function would call itself infinitely (until the program crashes).

[!IMPORTANT] Infinite Recursion: If a recursion never reaches a base case, it will lead to a RecursionError: maximum recursion depth exceeded.

3. Classic Example: Factorial

Calculating the factorial of a number (n!) is the most common way to demonstrate recursion. Example: 5! = 5 * 4 * 3 * 2 * 1 = 120

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

print(factorial(5)) # Output: 120

4. More Examples

A. Fibonacci Sequence

The Fibonacci sequence is a series where each number is the sum of the two preceding ones (0, 1, 1, 2, 3, 5, 8...).

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

# Print first 10 numbers
for i in range(10):
    print(fibonacci(i))

B. Sum of a List

Recursively adding numbers in a list.

def sum_list(numbers):
    if not numbers: # Base Case: Empty list
        return 0
    else:
        return numbers[0] + sum_list(numbers[1:])

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

C. String Reversal

Reversing a string character by character.

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

print(reverse_string("Hello")) # Output: olleH

5. Visualizing Recursion (Mental Model)

Recursion works like a stack of papers. Each function call adds a new page on top. The program only starts "finishing" the work once it hits the base case and begins removing pages from the top of the stack.

| Advantages | Disadvantages | | :--- | :--- | | Clean and elegant code | Can be hard to debug | | Breaks complex tasks into sub-problems | Highly memory intensive | | Great for tree/graph traversals | Risk of "Stack Overflow" |

6. Recursion Limit

Python has a default limit on how many times a function can call itself (usually 1000). You can check and change this using the sys module.

import sys
print(sys.getrecursionlimit())

# To increase it (use with CAUTION):
# sys.setrecursionlimit(2000)

7. Summary Logic

1. Understand the problem: Can it be broken down?
2. Define Base Case: When should it stop?
3. Define Recursive Case: How does it call itself with a smaller problem?