MASTER YOUR LOGIC BUILDING:Phase 3 - Level 1: Basic Recursion

Phase 3 - Level 1: Basic Recursion

Why Recursion Matters

Imagine Russian nesting dolls — open one doll and there's a smaller one inside, until you reach the tiniest doll that doesn't open. Recursion works the same way: a function solves a big problem by calling itself on a slightly smaller version of the same problem, until it hits something so simple it can answer directly.

If loops are like walking step by step down a hallway, recursion is like saying: "I'll handle this step after someone handles the rest — and that someone is me, on a shorter hallway."

What You'll Learn

• What base case and recursive case mean (and why both are required)
• How to trust the smaller case instead of tracing every call in your head
• Basic patterns: printing sequences, factorial, simple sums

The Two Parts Every Recursive Function Needs

1. Base Case — When to Stop

This is the smallest doll — the problem so tiny you can answer without calling yourself again.

if n == 0:
    return  # or return 1, or return some fixed value

Without a base case, Python keeps calling the function forever until you get a RecursionError. Always define your stop condition first.

2. Recursive Case — Trust the Smaller Problem

You don't solve the whole thing at once. You make the problem one step smaller and trust that the recursive call returns the right answer.

def factorial(n):
    if n == 0 or n == 1:      # base case
        return 1
    return n * factorial(n - 1)  # trust factorial(n-1) is correct

Think: factorial(5) = 5 × factorial(4). You don't need to manually compute factorial(4) — you trust the function handles it.

Step-by-Step Thinking Process

When writing any recursive function, ask yourself:

1. What's the simplest input? (That's your base case.)
2. How do I make the input smaller? (Usually n - 1, n // 10, or a shorter string.)
3. How do I combine the smaller answer with the current step?

Example — print 1 to n:

def print_1_to_n(n):
    if n == 0:           # base: nothing left to print
        return
    print_1_to_n(n - 1)  # trust: 1..n-1 prints correctly
    print(n)             # then print this number

Common Mistakes & Tips

• Forgetting the base case — the #1 beginner bug. Write it first.
• Not moving toward the base case — if you call f(n + 1) instead of f(n - 1), you never stop.
• Trying to trace 20 levels deep — you only need to believe: "If the smaller case works, my case works."
• Tip: Say the logic out loud: "To solve n, I first solve n-1, then do one more thing."

Practice Focus

Work through the examples below — Print 1 to N teaches order of calls (recurse first, act second), and Factorial teaches combining a result with the recursive answer. Run them, change n, and watch how the base case stops the chain.