What is the main idea behind recursion and base cases?

It is the practice of using Python's recursive calls and termination conditions deliberately, understanding the behavior of each operation, and testing that the result matches the intended requirement.

How would you check whether an example is correct?

Read it line by line, predict the result, run it with representative inputs, compare the actual result with the expected output, and test relevant edge cases.

PythonAlgorithms and Capstone Practicebeginner22 min read

Recursion and Base Cases

Learn recursive calls and termination conditions with clear explanations, runnable examples, and practice.

In this lesson, you will learn:

Explain the purpose of recursive calls and termination conditions.
Read and trace a short Python example in execution order.
Predict and verify the exact output of the lesson's examples.
Apply the concept to a small practice task and explain the solution.

1. Core idea

This lesson focuses on recursive calls and termination conditions. Start by understanding the purpose of the concept before memorizing syntax.

In Python, recursive calls and termination conditions should be learned by reading small examples, predicting the result, and then checking that result. The goal is to understand why the program behaves as it does.

Worked example

python

1
2
3
4
5
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)
print(factorial(5))

Output

120

This example demonstrates recursive calls and termination conditions. Read the code from top to bottom and identify the value produced by each expression. Compare the displayed output with the exact output shown here; spaces and line breaks are significant.

2. Step-by-step reasoning

Read each statement in execution order. Python evaluates expressions and then performs the operation described by the statement.

When the example changes a value, track the relevant name or collection after each statement. When it branches or loops, check the condition at the exact point where Python evaluates it.

A base case stops recursion

python

1
2
3
4
5
6
def countdown(n):
    if n == 0:
        return
    print(n)
    countdown(n - 1)
countdown(3)

Output

3 2 1

Each call decreases n by one. When n reaches zero, the base case returns without another call.

Key Point

Keep the distinction between syntax, runtime behavior, and coding convention clear while studying recursion and base cases.

Step-by-Step Execution Dry Run

Trace how Python executes each statement and modifies memory state.

Step	Code Line	Variable State / Output	What Python Does
#1	`def factorial(n):`	Initial expression or statement	Python begins by evaluating the first statement.
#2	`print(factorial(5))`	Final operation	The final statement produces or displays the result shown in the output.

3. Practical use and edge cases

Use recursive calls and termination conditions when it makes the program's intent clearer and its behavior easier to test.

Test ordinary values as well as boundary cases. For example, consider empty input, zero, negative values, missing keys, or an empty collection when those cases apply to the operation.

Prefer small, descriptive names and focused functions. Clear code is easier to debug than a compact expression whose behavior is difficult to explain.

Common Mistake to Avoid

Do not assume that code is correct only because it runs once. Check expected output, important edge cases, and the behavior of invalid values when the concept accepts external input.

Common Pitfalls & Mistakes to Avoid

#1 Memorizing syntax without understanding the behavior.

Explanation: Trace each statement and explain what value or state changes after it runs.

#2 Assuming the displayed output without checking spaces, types, or line breaks.

Explanation: Run the example and compare the actual output character by character.

#3 Ignoring edge cases or invalid values.

Explanation: Test representative normal, boundary, and invalid cases when they apply.

Practice Questions

Write recursive countdown(n) that prints n and stops when n <= 0; call it with 2.

Re-create the behavior demonstrated in the second example: A base case stops recursion. Use the code and expected output as your acceptance criteria.