Python Recursion Exercises

You are exploring recursion in Python, a technique where a function calls itself to solve smaller instances of a problem. Recursion is commonly used for tasks like traversing trees, calculating factorials, and solving divide-and-conquer problems.

However, one critical aspect of recursion is ensuring that the function eventually stops calling itself, or it will lead to an infinite loop and a stack overflow error.

In this context, what is the base case in a recursive function?

The part of the function that calls itself repeatedly in a loop.

The condition under which the function stops calling itself and returns a result directly.

The loop that executes indefinitely until manually stopped.

The main function that is called when the Python program starts running.

The base case in a recursive function is the condition that allows the function to stop calling itself and begin returning results. It is essential to prevent infinite recursion and is the point where the recursion starts to unwind.

For example:

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

Here, n == 0 is the base case. Without it, the function would keep calling factorial(n - 1) indefinitely, eventually causing a recursion depth error.

A well-designed recursive function must always include a base case to ensure it eventually terminates.

Which of the following is a simple recursive function to calculate the factorial of a number?

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

def factorial(n):
    return n * factorial(n)

def factorial(n):
    return 1

This function uses recursion correctly with a base case when n == 0. It multiplies n with factorial(n - 1) until the base case is reached.

What will be the output of this code?

def print_numbers(n):
    if n == 0:
        return
    print(n)
    print_numbers(n - 1)

print_numbers(3)

3 2 1

1 2 3

0 1 2 3

Infinite loop

The function prints n before making the recursive call. So it prints 3, then 2, then 1. When n becomes 0, the function returns and recursion stops.

What is a key risk of writing a recursive function without a base case?

The function will return 0

It may run too quickly

It will result in infinite recursion and a stack overflow

The function will exit early

If a recursive function lacks a base case, it will keep calling itself indefinitely, eventually causing a stack overflow error.

Which built-in Python error occurs when maximum recursion depth is exceeded?

TypeError

RecursionError

SyntaxError

NameError

Python raises a RecursionError when a recursive function exceeds the maximum call stack limit to prevent crashing the interpreter.

What will be the output of the following function call?

def sum_digits(n):
    if n == 0:
        return 0
    return n % 10 + sum_digits(n // 10)

print(sum_digits(1234))

10

1234

6

7

The function adds each digit of the number recursively. For 1234: 4 + 3 + 2 + 1 = 10.

How many times will the function be called in total when calling count_down(4)?

def count_down(n):
    if n == 0:
        return
    count_down(n - 1)

3

4

5

Infinite

The function is called once for each number from 4 to 0. So it's called 5 times in total: for 4, 3, 2, 1, and 0.

Which of the following is an example of tail recursion?

def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)

def fact(n, acc=1):
    if n == 0:
        return acc
    return fact(n - 1, acc * n)

def sum(n):
    return sum(n - 1) + n

def print_n(n):
    if n > 0:
        print(n)

Tail recursion means the recursive call is the last operation in the function. In Option 2, the function returns the recursive call directly, making it a tail-recursive function.

Which statement about recursion is FALSE?

Every recursive function must have a base case

Recursive functions can call themselves multiple times

Recursion is always more efficient than iteration

Recursion can be used to solve problems that can be broken into subproblems

Recursion is not always more efficient. In many cases, especially with large call stacks or lack of memoization, recursion can be slower and consume more memory than iteration.

What does this recursive function compute?

def mystery(n):
    if n == 0:
        return 1
    return 2 * mystery(n - 1)

n factorial

2 raised to the power of n

Sum of 1 to n

Product of even numbers up to n

The function returns 2 multiplied by the result of the same function with n - 1. This forms the pattern 2ⁿ. For example, mystery(3) = 2 * 2 * 2 * 1 = 8.

What is the output of the following recursive function call?

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

print(func(6))

13

8

21

5

This function is a classic implementation of the Fibonacci sequence. func(6) = 5 + 3 + 2 + 1 + 1 + 0 = 13. The sequence follows: 0, 1, 1, 2, 3, 5, 8...

What is the time complexity of a naive recursive Fibonacci function (without memoization)?

O(n)

O(n log n)

O(2ⁿ)

O(log n)

The naive recursive Fibonacci function makes two recursive calls for each non-base case, leading to an exponential time complexity of O(2ⁿ).

What does the following recursive function compute?

def compute(n):
    if n == 1:
        return 3
    return 3 + compute(n - 1)

n³

3 × n

3ⁿ

n!

The function adds 3 to itself n times starting from 1. This is equivalent to computing 3 × n using recursion.

Which of the following best describes mutual recursion?

Two or more functions calling each other in a recursive manner

Function that calls itself directly

Function that uses iteration within recursion

Recursive function using only one base case

Mutual recursion occurs when two or more functions call each other in a recursive manner. For example, function A calls function B, and function B calls function A.

Which of the following scenarios is recursion better suited for than iteration?

Calculating sum of two numbers

Reversing a list

Traversing a tree structure

Iterating through a for loop 10 times

Recursive approaches are often ideal for problems that involve hierarchical or branching structures, such as trees. Tree traversal (like DFS) is naturally expressed using recursion.

What will be the output of the following function call?

def strange(n):
    if n <= 0:
        return 0
    print(n)
    strange(n - 2)
    print(n)

Function call: `strange(4)`

4 2 0 2 4

4 2 2 4

4 2 2

4 2 0

The function prints n, then recurses with n-2, and after the recursive call, prints n again. So the sequence is: print(4), print(2), base case, then print(2), print(4).

What is the output of the following code?

def fun(x):
    if x % 2 == 0:
        return x
    else:
        return fun(x - 1)

print(fun(5))

5

4

3

Error

The function keeps subtracting 1 until x becomes even. 5 is odd, so it calls fun(4), which is even, and returns 4.

What is the result of this code?

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

print(recurse(20, 8))

4

0

2

8

This is a recursive implementation of the Euclidean algorithm to find the GCD. recurse(20, 8) → recurse(8, 4) → recurse(4, 0) → returns 4.

What will the following code print?

def mystery(n):
    if n == 1:
        return 1
    print(n, end=" ")
    return mystery(n // 2)

mystery(20)

20 10 5 2

1 2 5 10 20

20 10 5 2 1

1

The function prints the current number then recurses with integer division by 2. Once it reaches 1, it stops printing because the return happens before the print.

Which recursive function will cause a stack overflow faster than others for large input n?

def count(n):
    if n == 0:
        return 0
    return 1 + count(n - 1)

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

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

def print_num(n):
    if n > 0:
        print(n)

The recursive Fibonacci function without memoization makes an exponential number of calls, leading to a stack overflow much faster than linear-recursive functions like factorial or count.

You are exploring recursion in Python, a technique where a function calls itself to solve smaller instances of a problem. Recursion is commonly used for tasks like traversing trees, calculating factorials, and solving divide-and-conquer problems.

However, one critical aspect of recursion is ensuring that the function eventually stops calling itself, or it will lead to an infinite loop and a stack overflow error.

In this context, what is the base case in a recursive function?

Which of the following is a simple recursive function to calculate the factorial of a number?

What will be the output of this code?

What is a key risk of writing a recursive function without a base case?

Which built-in Python error occurs when maximum recursion depth is exceeded?

What will be the output of the following function call?

How many times will the function be called in total when calling count_down(4)?

Which of the following is an example of tail recursion?

Which statement about recursion is FALSE?

What does this recursive function compute?

What is the output of the following recursive function call?

What is the time complexity of a naive recursive Fibonacci function (without memoization)?

What does the following recursive function compute?

Which of the following best describes mutual recursion?

Which of the following scenarios is recursion better suited for than iteration?

What will be the output of the following function call?

Function call: strange(4)

What is the output of the following code?

What is the result of this code?

What will the following code print?

Which recursive function will cause a stack overflow faster than others for large input n?

About This Exercise: Python – Recursion

Function call: `strange(4)`