Base case and the call stack in Python

Why it matters

Recursion is the tool behind trees, graphs, divide and conquer, and backtracking. Interviewers use it to check whether you can reason about a function that calls itself. Many beginners can follow a loop but freeze when a function calls itself, because it is hard to picture what happens next. This lesson removes that fear. You will learn one rule, one picture, and one habit, and you will be able to predict the output of a recursive function before you run it.

The idea from the first principle

Start with a plain question. Suppose you want to add the numbers from 1 to 5. You could write a loop. Or you could notice something: the sum of 1 to 5 is 5 plus the sum of 1 to 4. The sum of 1 to 4 is 4 plus the sum of 1 to 3. This pattern repeats until the list is empty or the number is zero, and at that point the answer is known without any more work.

A function is a named block of Python code, written with def. A recursive function is a function that calls itself to solve a smaller copy of the same problem. The word "recursion" comes from the Latin for running back. The function runs back into itself.

Recursion is not magic. It always has two parts:

1. The base case. This is the input so small that the answer is known directly. It is the place where the chain of calls stops.
2. The recursive case. This is the part where the function calls itself with an input that is closer to the base case.

If you have only the second part, the chain never stops. If you have only the first part, the function never does any real work. You need both.

Think of a set of Russian dolls, the wooden ones where each doll opens to reveal a smaller one. Suppose you want to know how many dolls are inside the biggest one, and you are not allowed to count them all at once. You open the biggest doll, look inside, and ask the same question of the doll you find. Each doll asks the question of a smaller doll. The smallest doll has nothing inside, so it answers "zero" immediately. That smallest doll is the base case. Every doll above it adds one to the answer it receives.

Here is the same idea written as a rule you can check:

• Ask: what does this function return for the smallest input? That is the base case.
• Ask: if I already knew the answer for a smaller input, how would I get the answer for this input? That is the recursive case.
• Check: does every call move toward the base case? If not, the function never stops.

A useful habit is to say the rule out loud before you write any code. For the dolls: "The number of dolls inside the doll I am looking at is one plus the number inside the doll it contains, unless it contains nothing, in which case the answer is zero." Once that sentence is clear, the Python code almost writes itself.

Your first recursive function: factorial

The factorial of a whole number n, written n!, is n * (n - 1) * ... * 1. So 5! is 5 * 4 * 3 * 2 * 1, which is 120. By definition 0! is 1. That definition is what makes the base case clear.

Apply the rule from the last section. The smallest input is n == 0, and the answer for that input is 1. For any other n, the factorial is n times the factorial of n - 1. That gives this function:

Press Run. This program needs no input. You should see:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120

Read the function slowly. The keyword def starts a function definition. The name factorial is what you call it by. The parameter n is the input. The text -> int is a type hint. It tells readers and tools that the function returns a whole number. Python does not check type hints while the program runs, so -> int is a note, not a rule. Inside the function, if n == 0 checks the base case, and return 1 gives the answer straight away. The last line returns n * factorial(n - 1). Python first works out factorial(n - 1), waits for the answer, multiplies by n, and returns that product.

The double equals sign == in n == 0 means "is equal to". A single equals sign = means "store this value in". Beginners mix these up often. If you write if n = 0:, Python stops with a SyntaxError before the program runs, because it cannot use a store operation as a test.

Tracing factorial by hand

A trace is a step-by-step record of what the function does with each value. Tracing is the main skill in this lesson. You can trace on paper, and you should, before you trust the code.

Here is the trace for factorial(3). Read it from the top down. Each indented line is a call that is waiting for the call below it to finish.

factorial(3) waits for factorial(2)
  factorial(2) waits for factorial(1)
    factorial(1) waits for factorial(0)
      factorial(0) returns 1
    factorial(1) returns 1 * 1 = 1
  factorial(2) returns 2 * 1 = 2
factorial(3) returns 3 * 2 = 6

The trace has two halves. On the way down, each call makes a new call and waits. This is the descent. At the bottom, the base case returns a value without waiting for anything. Then the values travel back up, and each waiting call finishes its multiplication. This is the unwinding. Once you can see both halves, you can predict any recursive function.

Notice that factorial(1) finishes before factorial(2) does. The multiplications happen in reverse order of the calls. That reversal is not an accident. It is how the call stack works, and it is the subject of the next section.

What happens inside: the call stack

Python keeps track of active function calls in a region of memory called the call stack. A stack is a pile. You can add something to the top, and you can remove only the top item. If you think of a stack of plates in a canteen, you take the top plate, and when you add a plate you put it on top.

Each function call gets its own box of memory, called a frame. A frame holds the function's parameters and its local variables. When factorial(3) runs, its frame holds n equal to 3. When it calls factorial(2), Python pushes a new frame on top, and that frame holds its own n equal to 2. The two n values are separate boxes. They do not interfere with each other, even though the name is the same.

When a call returns, its frame is popped off the top. The call below it then continues from the place where it stopped.

Here is the picture for factorial(3) at the moment the base case is running. The newest call is at the top:

+----------------------+
| factorial(0)  n = 0  |  <- top: running, returns 1
+----------------------+
| factorial(1)  n = 1  |  waiting for factorial(0)
+----------------------+
| factorial(2)  n = 2  |  waiting for factorial(1)
+----------------------+
| factorial(3)  n = 3  |  waiting for factorial(2)
+----------------------+
| <module>             |  the main program, waiting
+----------------------+

Only the top frame is doing work. The frames below it are waiting. When the top frame returns 1, it is removed, and the frame below it, factorial(1), can finish its multiplication. The order is last in, first out. Computer scientists call this LIFO, which means the last item pushed is the first item popped.

Follow the rest of the picture in your head. The frame for factorial(0) returns 1 and is removed. The frame for factorial(1) is now on top. It computes 1 times 1 and returns 1. That frame is removed. The frame for factorial(2) computes 2 times 1 and returns 2. Then factorial(3) computes 3 times 2 and returns 6 to the main program.

Here is the consequence. When a recursive function is running, the memory used by the stack grows with the number of calls that are still waiting. For factorial(n), that means n + 1 frames at the deepest point. Python limits the depth on purpose. The limit is stored in the sys module, and you can read it like this:

import sys
 
print(sys.getrecursionlimit())

On the Python 3.14 used to check this lesson, the output is 1000. When a recursion goes deeper than the limit, Python stops it with a RecursionError. You will see that error shortly. The limit is a safety net, so that a broken function fails quickly instead of using up all the memory on the computer.

Before or after the recursive call

Where you put a statement inside a recursive function matters. A statement placed before the recursive call runs on the way down. A statement placed after the call runs on the way back up. This is one of the most common sources of confusion, so it is worth a clear example.

Here is a function that prints a countdown, with one line before the recursive call and one line after it:

Press Run. The program needs no input. It prints:

down 3
down 2
down 1
up 1
up 2
up 3

Trace it once. countdown(3) prints "down 3", then calls countdown(2), which prints "down 2", then calls countdown(1), which prints "down 1", then calls countdown(0). The base case returns at once and prints nothing. Now countdown(1) continues past its call and prints "up 1". Then countdown(2) prints "up 2", and countdown(3) prints "up 3". The up lines come out in reverse order because the calls return in reverse order.

The return in the base case has no value. The -> None in the header says that the function returns nothing. A function like this returns None, which is Python's word for "no value". Using return alone leaves the function early.

This pattern, doing work on the way down and on the way up, is useful. Printing a tree in order uses it. Reversing a string using recursion uses it. You will see it again in the next lesson and in the tree lessons that follow this module.

Writing a recursive function step by step

Now let us write a new function from nothing, using a fixed process. The problem: add the numbers from 1 up to n. For n equal to 4 the answer is 1 + 2 + 3 + 4, which is 10.

Follow four steps every time you write a recursive function:

1. Name the answer. The function sum_to(n) returns the sum of the numbers from 1 to n.
2. Find the smallest input and its answer. When n is 0, there are no numbers to add, so the sum is 0.
3. Write the reduction. The sum from 1 to n is n plus the sum from 1 to n - 1. This step is the recursive case.
4. Check that each call moves toward the base case. Each call reduces n by 1, so after n calls the value reaches 0.

Put those steps into code. This version uses a fixed number so that it can run without input. To read the number from the user instead, replace the value 10 with int(input()), which reads one line from the input box and turns it into a whole number:

The output is:

1 + 2 + ... + 10 = 55
1 + 2 + ... + 0 = 0

Check the function against the four steps. The answer is named sum_to. The base case n == 0 returns 0. The reduction n + sum_to(n - 1) is the recursive case. Each call lowers n by 1, so the calls always reach the base case when n is zero or more.

The function has one weakness, and it matters. If you pass -3, the value of n never becomes 0. It goes to -1, -2, -3 and on forever, so the function runs out of stack frames. An interviewer would ask you whether your function handles negative input. A complete answer is to check for it at the start and reject it, for example with if n < 0: raise ValueError("n must be 0 or more"), or to state in a comment that the function expects n >= 0. Writing that down is a sign of care.

Two parameters that change together: power

A recursive function can have more than one parameter. The base case may then depend on one of them, while the other one changes on each call. A good example is power(base, exp), which computes base raised to the power exp. For example, 2 to the power 10 is 1024, because you multiply 2 by itself ten times.

The smallest input is exp == 0, and any number to the power 0 is 1. For a bigger exponent, base ** exp is base times base ** (exp - 1). The exponent falls by one on each call, and the base stays the same.

Press Run. The output is:

1024
1
343
1099511627776
1267650600228229401496703205376

Python does not have a fixed-size whole number type. An int in Python grows to whatever size the number needs, so 2 ** 100 is printed in full. In Python, a big integer result does not need a special type, and you never get a silent wrong answer from overflow.

Trace power(7, 3) on paper. The calls are power(7, 3), then power(7, 2), then power(7, 1), then power(7, 0). The base case returns 1. Then power(7, 1) computes 7 * 1 = 7, power(7, 2) computes 7 * 7 = 49, and power(7, 3) computes 7 * 49 = 343.

This function makes exp + 1 calls, so its time cost is O(exp), and its stack cost is also O(exp). There is a faster version that squares the base at each step, and it needs only about log2(exp) calls. That faster version is a good interview follow-up, but the simple version is the right first step because the structure is easy to check. Python also has the built-in ** operator, which is written in C and is much faster than any recursive version. Use ** in real code. Write the recursive version to learn the pattern.

Counting calls: why fib is expensive

The Fibonacci numbers are a classic recursion example. Each number is the sum of the two before it, starting with 0 and 1: 0, 1, 1, 2, 3, 5, 8, 13, and so on. The recursive definition is short:

fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)

The code follows the definition exactly. But there is a hidden cost. Each call to fib(n) makes two more calls, so the number of calls grows very fast. To see how fast, count the calls. The next program uses a global variable named calls. The keyword global lets the function change a variable that lives outside it. The program prints the number of calls for fib(10) and for fib(4).

Press Run. The output is:

fib(10) = 55
calls made = 177
fib(4) = 3
calls made = 9

The global counter calls is shared by every call, so it counts all of them. The calls += 1 line is the first thing in the function, so it counts every call, including base case calls. You can check the 9 for fib(4) by drawing the tree. fib(4) calls fib(3) and fib(2). fib(3) calls fib(2) and fib(1). The two copies of fib(2) each call fib(1) and fib(0), and so on. The tree has 9 nodes in total. The number of calls for fib(n) is always 2 * fib(n + 1) - 1, which for n equal to 10 gives 2 * 89 - 1 = 177.

That number grows about 1.6 times as fast with each step of n, and the time cost is O(2^n), which is an exponential cost. For n equal to 40 you would wait a long time. The reason is repetition: fib(3) is computed again and again inside fib(5). The fix, called memoization, is the subject of the next lesson. For now, learn the warning sign. A recursive function that makes two calls on each step, and calls the same smaller inputs again, can be exponential.

Here is the call tree for fib(4) written as text, with repeated nodes shown:

fib(4)
  fib(3)
    fib(2)
      fib(1)
      fib(0)
    fib(1)
  fib(2)
    fib(1)
    fib(0)

Count the lines: 9. The node fib(2) appears twice, and so does fib(1).

Stack overflow: when the recursion goes too deep

Each call takes space on the stack. Python limits the stack to the recursion limit from the earlier section, which is 1000 frames by default. When a recursion goes deeper than that, Python stops the program with an error called RecursionError. The message is maximum recursion depth exceeded.

The following program makes a function call itself forever. It catches the error so that you can see what happens without the program stopping:

Press Run. The output is:

caught: maximum recursion depth exceeded
went deeper than 100 calls: True
recursion limit: 1000

The try and except lines are a way to handle an error. Code inside try runs normally. If an error of the named type happens, Python jumps to the except block. The name after as (here e) holds the error object, and print("caught:", e) shows its message. Most of the time you do not catch RecursionError. You fix the recursion instead. Catching it here shows you the error without ending the program.

In practice, a missing base case produces a traceback like this when the error is not caught. The example below comes from a function sum_no_base(n) that has no base case. The file path and the marker lines under each code line depend on where you save the file and on your Python version, so your output may look a little different:

Traceback (most recent call last):
  File "sum_no_base.py", line 5, in <module>
    sum_no_base(5)
    ~~~~~~~~~~~^^^
  File "sum_no_base.py", line 2, in sum_no_base
    return n + sum_no_base(n - 1)
               ~~~~~~~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

The last line tells you what went wrong. Read upward from it. The line [Previous line repeated 996 more times] tells you that the same frame was active many times, so the bug is in the function named in that repeated frame. Here it is line 2, the recursive call. When you see a long traceback that repeats the same line, you have almost certainly got a recursion with a missing or unreachable base case. Go to the repeated line first.

Common mistakes

Recursion mistakes look simple once you see them, but they are easy to make when you are new. These are the ones that appear most often, with the real messages you will see.

No base case. A function with no reachable base case calls itself until the limit is reached. The message is the RecursionError shown above. The fix is to write the base case first, before the recursive case, and to check that the input moves toward it.

The base case is never reached. This is subtler. A function with a base case of n == 0 that is called as sum_to(n + 1) moves away from zero, so it never stops. The message is the same. Read the call, then ask: does each call make the input smaller, in the direction of the base case? If not, flip the sign of the step.

The missing return. When you write the recursive case, you must return the value. A line like n * factorial(n - 1) without return is valid Python, so it does not fail when you save the file. The function then returns None on every call that reaches that line, and the multiplication fails. This is the real error when that line is in a function that is called with 3:

Traceback (most recent call last):
  File "factorial.py", line 7, in <module>
    print(factorial(3))
          ~~~~~~~~~^^^
  File "factorial.py", line 4, in factorial
    n * factorial(n - 1)
        ~~~~~~~~~^^^^^^^
  File "factorial.py", line 4, in factorial
    n * factorial(n - 1)
    ~~^~~~~~~~~~~~~~~~~~
TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'

The message says that * got an int on the left and None on the right. The None is the value that factorial(1) returned. That call computed 1 * factorial(0) but had no return in front of it, so it gave back nothing. The fix is to add return before the expression. Read the message: the type name NoneType is the clue that a function returned nothing.

Floats overflow, ints do not. Python's int type has no size limit, so a big whole-number answer is always correct. A float is different. It stores decimal numbers with a fixed size, and it stops at about 1.8 times 10 to the power 308. A recursion that multiplies floats can therefore fail with this error:

Traceback (most recent call last):
  File "float_overflow.py", line 1, in <module>
    print(2.0 ** 1100)
          ~~~~^^~~~~~
OverflowError: (34, 'Numerical result out of range')

If you write 2 ** 1100 with whole numbers, Python prints the full answer instead. Use int for counts and factorials, and use float only when the answer is a measurement.

Printing the wrong order. This is not a crash, so it is harder to notice. If you put print after the recursive call, your lines come out reversed. Check whether each print runs on the way down or on the way up, using the trace method from this lesson.

Debugging walkthrough

Suppose a friend gives you this function and says it sometimes crashes. They want the sum of 1 to n, and it works for 3 but fails for 0.

def sum_to(n: int) -> int:
    if n == 1:
        return 1
    return n + sum_to(n - 1)

Use the four steps from the earlier section. First, name the answer: the function should return the sum from 1 to n. Second, find the smallest input. The base case here is n == 1, which returns 1, and that is correct for input 1. But what about input 0? The function has no rule for 0, so the call sum_to(0) goes to sum_to(-1), then sum_to(-2), and never reaches 1. That is the bug: the base case does not cover every input the function can receive.

To prove the diagnosis, add a print line at the start of the function so that you can watch each call. This is the most common debugging move for recursion, and it costs nothing. Here is the instrumented version, which you can run:

The output is:

enter sum_to(3)
enter sum_to(2)
enter sum_to(1)
result 6

The trace shows the descent clearly: three entries, one per call, and then the result comes back up as 3 + 2 + 1 = 6. The trace also shows what would go wrong with input 0. You would see enter sum_to(0), then enter sum_to(-1), and the lines would keep appearing until the RecursionError. The fix is to change the base case to n == 0 with return 0, which handles every input from zero upward. A print on entry helps you find where a recursion goes wrong, and you can remove the print once the trace looks right.

Notice what the debugging did not do. It did not guess at a fix. It first named the expected answer, found the input where the expectation fails, and then watched the calls. Keep that order in every recursion bug.

Cost in plain numbers

Recursion has two costs. The first is time: how many calls are made. The second is space: how many frames sit on the stack at the deepest point.

For factorial(n) and sum_to(n), each call makes one more call. So there are n + 1 calls in total, and the time is O(n). At the deepest point, there are n + 1 frames on the stack, so the stack space is O(n). A loop that does the same work uses O(1) space, because it reuses one variable. This is one reason interviewers ask whether a recursive solution can be turned into a loop.

For plain fib(n), each call makes two more calls, and the number of calls grows exponentially, as O(2^n). Its stack depth is only O(n), because the depth is the length of the longest chain of calls, which is n. The problem is the total work, not the depth.

When you estimate the cost of a recursive function, count two things: how many calls there are in total, and how deep the chain of waiting calls gets. Those two numbers answer most questions about time and space.

Interview and real-world uses

In interviews, recursion is usually the first answer to a problem about a tree or a split input, and the interviewer then asks you to state the base case, the recursive case, the time cost and the space cost. You should be able to say all four in one breath. For example: "The base case is an empty list, which returns 0. The recursive case adds the first element to the sum of the rest. It makes n calls, so the time is O(n), and the stack depth is O(n)." That answer shows the interviewer that you understand the mechanism, not only the code.

In real software, recursion appears in file system walks (a folder contains folders), in parsing expressions (a bracket contains an expression), in JSON handling (an object contains objects), and in compilers. Many production systems avoid deep recursion on untrusted input, because an attacker can send input that is deep enough to hit the recursion limit. If you see a function that recurses on user input without a depth limit, that is a warning sign.

Reading a recursive call without getting lost

Beginners often try to follow every call in their head at once, and that is why recursion feels impossible. A better way is to read a recursive call the way you read a call to any other function. When you see power(base, exp - 1), do not dive into it. Assume that it returns the correct answer for the smaller input, and ask only how you use that answer. This is sometimes called the leap of faith. It is safe when two conditions hold: the base case returns the right answer directly, and every call moves toward the base case. If those two things are true, the function is correct for every input, because the reasoning repeats for each size.

The power function is a good example to practise this habit. Suppose you have just written it, and you want to check it for exp equal to 3. Read the recursive line as a promise: "power(base, exp - 1) gives me the right value for one smaller exponent." You then only need to check the combining step, which multiplies that value by base.

A trace table makes the promise visible. Each row is one call, and each row uses the row below it:

Read the table from the bottom up. The bottom row is the base case, and every row above it multiplies the value below by 7. This matches the program output of 343 for power(7, 3) shown earlier in the lesson. A table like this takes a minute to write, and it catches almost every mistake in a simple recursive function before you run the code.

The same table idea works for any recursion. Make a column for the input, a column for the answer, and fill in the base case first. Then move up one row at a time. If your table gives a different answer from what the program prints, the bug is in one of the rows, and you can find it by comparing each row with the code.

Keep one more habit for later modules. When a recursion has a loop inside it, as the backtracking functions do, the table grows sideways as well as down. Each row then has several children, and the same reading applies to each child. You will see this in the subset and permutation lessons.

Practice

Exercise 1 (easy). Write sum_to(n) that returns 1 + 2 + ... + n, using the base case n == 0. Run it for 10 and check that it prints 55.

Show the answer

def sum_to(n: int) -> int:
    if n == 0:
        return 0
    return n + sum_to(n - 1)
 
 
print(sum_to(10))  # 55

The base case returns 0 for n == 0. The recursive case adds n and the sum of the rest. Each call lowers n by one, so the chain always stops.

Exercise 2 (easy). Write power(base, exp) using recursion, with exp going down by one each call. Check that power(2, 5) returns 32.

Show the answer

def power(base: int, exp: int) -> int:
    if exp == 0:
        return 1
    return base * power(base, exp - 1)
 
 
print(power(2, 5))  # 32

The base case handles exp == 0, which is why power(5, 0) returns 1. Python integers do not overflow, so the same function works for large results.

Exercise 3 (easy). Before you run it, write down exactly what this prints for countdown(2), then run it to check: countdown prints "down n" before the recursive call and "up n" after it, and returns when n is 0.

Show the answer

down 2
down 1
up 1
up 2

The "down" lines run on the way in, in the order 2, then 1. The "up" lines run on the way out, starting with the innermost call, so 1 comes before 2.

Exercise 4 (medium). Write count_digits(n) that returns how many decimal digits n has, using recursion. Hint: a number with more than one digit has the same digit count as n // 10 plus one. Check that 0 has 1 digit, and that 12345 has 5.

Show the answer

def count_digits(n: int) -> int:
    if n < 10:
        return 1
    return 1 + count_digits(n // 10)
 
 
print(count_digits(0))      # 1
print(count_digits(12345))  # 5

The base case is any number from 0 to 9, which has one digit. Each call uses //, the floor division operator, which removes the last digit. For 12345 the calls go 12345, 1234, 123, 12, 1, and the answer is 5.

Exercise 5 (medium). Write a recursive function print_binary(n) that prints the binary form of a non-negative number, with no newline at the end. For example, print_binary(5) prints 101. Hint: print the binary of n // 2 first, then print n % 2. This is a "work on the way out" function.

Show the answer

def print_binary(n: int) -> None:
    if n < 2:
        print(n, end="")
        return
    print_binary(n // 2)
    print(n % 2, end="")
 
 
print_binary(5)  # 101

The base case prints 0 or 1 directly. The recursive call prints the higher bits first, and the last print adds the lowest bit. Because the print comes after the call, the digits appear in the right order. For 5 the calls go 5, 2, 1, and the output is 101. The end="" part stops print from adding a newline after each digit.

Exercise 6 (medium). Count the calls that fib(6) makes, using the counter program from this lesson. Predict the number with the formula 2 * fib(n + 1) - 1 before running the program.

Show the answer

The formula gives 2 * fib(7) - 1 = 2 * 13 - 1 = 25. Run the counter program with fib(6) in place of fib(10). It should print 25 calls. If your prediction differs, trace the tree for fib(6) by hand and find the place where your count went wrong.

Exercise 7 (medium). Write reverse_digits(n) for a non-negative number, so that reverse_digits(1230) returns 321. Hint: the last digit is n % 10. Use a second parameter to carry the answer down the calls, so that no work is needed on the way out. Explain why this version does not need a long type in Python.

Show the answer

def reverse_helper(n: int, acc: int) -> int:
    if n == 0:
        return acc
    return reverse_helper(n // 10, acc * 10 + n % 10)
 
 
def reverse_digits(n: int) -> int:
    return reverse_helper(n, 0)
 
 
print(reverse_digits(1230))  # 321

The accumulator acc carries the answer down the calls. For 1230 the calls take the digits 0, 3, 2, 1 in turn and build 0, 3, 32, 321. Python integers have no size limit, so a long input does not overflow.

Exercise 8 (hard). Explain, in two or three sentences, why sum_to(-1) fails when the base case is n == 0, and state the smallest change to the function that makes it raise a clear error instead of a RecursionError.

Show the answer

From -1 each call goes to -2, then -3, and so on, so n never equals 0. Python keeps adding frames until the recursion limit is reached and it raises RecursionError. The smallest fix is to check the input at the start: if n < 0: raise ValueError("n must be 0 or more"). Raising an error makes the problem visible at once, instead of after 1000 calls.

Exercise 9 (hard). A function f(n) prints n, then calls f(n - 2) when n > 0. Predict the output of f(5) and of f(4), then write the code for f and check your prediction. Explain what goes wrong if you forget the base case.

Show the answer

def f(n: int) -> None:
    if n <= 0:
        return
    print(n, end=" ")
    f(n - 2)
 
 
f(5)  # prints: 5 3 1
print()
f(4)  # prints: 4 2

f(5) prints 5 3 1. The call f(-1) hits the base case and returns without printing. For f(4) the output is 4 2, because f(0) also hits the base case. Without the base case, f(-1) would call f(-3), and the numbers would go down forever until RecursionError. The base case must catch every number the chain can reach, not only the starting value.

Exercise 10 (hard). Write a recursive function is_power_of_two(n) that returns True when n is 1, 2, 4, 8, and so on. Hint: divide by 2 while the number is even, and check the base case for 1. Decide what the function should return for 0 and for negative numbers, and handle those inputs.

Show the answer

def is_power_of_two(n: int) -> bool:
    if n < 1:
        return False
    if n == 1:
        return True
    if n % 2 != 0:
        return False
    return is_power_of_two(n // 2)
 
 
print([is_power_of_two(x) for x in [0, 1, 2, 6, 8, -4]])

The output is [False, True, True, False, True, False]. Zero and negative numbers are rejected first, so the chain never gets stuck dividing 0 or a negative number. An odd number other than 1 is not a power of two. Each call halves the input, so the calls stop at 1 or at an odd number.

What you now know

• A recursive function solves a smaller copy of its problem, and it has a base case and a recursive case.
• The base case must be reachable from every input the function can receive, or the function fails with RecursionError.
• Each call adds a frame to the call stack. The stack is last in, first out, so the newest call finishes first.
• Statements before a recursive call run on the way down, and statements after it run on the way up.
• Factorial and sum take O(n) time and O(n) stack space. Plain Fibonacci makes O(2^n) calls because it repeats work.
• Python integers never overflow, but floats do. A missing return shows as a TypeError that mentions NoneType.
• To debug a recursion, name the expected answer, find the smallest input, and print on entry to watch the calls.