5.5 Recursive functions

In the logic of problem-solving, Recursion is a technique where a function calls itself to solve a smaller version of the same problem. It is based on the "divide and conquer" strategy: you break a complex problem into simpler sub-problems until you reach a version that is easy to solve directly.

1. The Two Essential Parts of Recursion

Every recursive function must have these two components to work correctly:

Base Case: The condition under which the function stops calling itself. Without a base case, the function will call itself infinitely, leading to a RecursionError (stack overflow).
Recursive Step: The part of the function where it calls itself with a modified (usually smaller) argument, moving closer to the base case.

2. Classic Example: Factorial

The factorial of a number n (written as n!) is defined as n × (n-1) × (n-2) × ... × 1.

Recursive Logic: n! = n × (n-1)!
Base Case: 0! or 1! = 1

Implementation:

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

print(factorial(5)) # Output: 120

3. How Recursion Works (The Call Stack)

When a function calls itself, Python doesn't finish the first call immediately. Instead, it "suspends" the current function and starts a new one. These suspended functions are stored in the Call Stack.

Winding Phase: The functions are added to the stack one by one until the base case is hit.
Unwinding Phase: Once the base case returns a value, the stack "unwinds," passing the result back up through each suspended function until the final answer is calculated.

4. Recursion vs. Iteration (Loops)

Feature	Recursion	Iteration (Loops)
Code Style	Elegant and shorter.	Longer and more explicit.
Memory	Uses more memory (stack).	Uses less memory.
Speed	Can be slower for simple tasks.	Generally faster.
Best For	Trees, sorting, complex math.	Repetitive tasks, counters.

5. Tracing Recursive Traces

Example A: Sum of Natural Numbers

def recursive_sum(n):
    if n == 1:
        return 1
    else:
        return n + recursive_sum(n - 1)

The Trace (Stack Winding):

recursive_sum(5) → 5 + recursive_sum(4)
recursive_sum(4) → 4 + recursive_sum(3)
... → until recursive_sum(1) returns 1 (Base Case Hit!)

The Unwinding: 1 → (2+1) → (3+3) → (4+6) → (5+10) = 15.

6. Practical Exercise Examples

Fibonacci Series

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

print(fibonacci(6)) # Output: 8

Reversing a String

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

print(reverse_string("PYTHON")) # Output: NOHTYP

Greatest Common Divisor (GCD)

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

print(gcd(48, 18)) # Output: 6

Summary Table: Recursive Mindset

Problem	Sample Base Case	Sample Recursive Step
Math Sum	n = 1	n + sum(n-1)
String	length = 0	reverse(rem) + first
Power	exp = 0	base * pow(rem)

Back to Course Syllabus

5.5 Recursive functions (BT101CO)