Which of the following function definitions shows the correct syntax for writing a recursive function in Python?
This question checks understanding of the syntax rules for recursion in Python:
Option 1: Correct ✅ – Defines a function with def, has a base case, and calls itself properly.
Option 2: Incorrect – Missing return for the recursive call; without it, results are lost.
Option 3: Incorrect – Invalid syntax because n func(n-1) is not a valid expression.
Option 4: Incorrect – Python does not use the keyword function; it uses def.
Key takeaway: A recursive function in Python must be defined with def, include a base case, and call itself with valid syntax using return.
Which of the following functions is recursive?
This question checks the ability to recognize a recursive function:
Option 1: Incorrect – Performs a calculation but does not call itself.
Option 2: Incorrect – Uses a loop to compute factorial, not recursion.
Option 3: Incorrect – A simple addition function, no self-calls.
Option 4: Correct ✅ – The function countdown calls itself with n-1, making it recursive.
Key takeaway: A function is recursive if it explicitly calls itself within its definition.
In a recursive function, what is the purpose of the base case?
This question checks the understanding of the base case in recursion:
Option 1: Incorrect – The base case is not about speed; it is about correctness and termination.
Option 2: Correct ✅ – The base case defines the condition where recursion stops, preventing infinite calls and stack overflow errors.
Option 3: Incorrect – Base cases do not change recursion into iteration; they just terminate recursion at the right point.
Option 4: Incorrect – That refers to memoization, not the base case.
Key takeaway: A base case ensures recursion terminates properly. Without it, the recursive function would run indefinitely and cause a stack overflow.
Which of the following statements about recursion is true?
This question tests the conceptual understanding of recursion:
Option 1: Incorrect – Recursion is widely used in many areas (tree traversal, sorting, searching), not only math.
Option 2: Correct ✅ – A recursive function needs a base case (to stop) and a recursive step (to continue until base case is reached).
Option 3: Incorrect – Recursion is not always faster; in fact, loops are usually more efficient in Python.
Option 4: Incorrect – Recursion relies heavily on the call stack, where each recursive call is stored until it returns.
Key takeaway: The essential structure of recursion is a base case and a recursive step; missing either leads to incorrect or infinite recursion.
What will be the output of the following recursive function call?
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
This problem tests understanding of recursion with the factorial function:
Step 1: factorial(4) = 4 * factorial(3)
Step 2: factorial(3) = 3 * factorial(2)
Step 3: factorial(2) = 2 * factorial(1)
Step 4: factorial(1) = 1 * factorial(0)
Step 5: factorial(0) = 1 (base case)
Now multiplying back:
4 × 3 × 2 × 1 = 24
Correct Answer: Option 4 ✅
Which of the following conditions is essential in every recursive function to prevent infinite recursion?
Every recursive function must include a base case. The base case is the condition that tells the function when to stop calling itself. Without it, the function would continue calling itself endlessly, leading to a RecursionError in Python.
Option 1: A return statement is important but not enough to stop infinite recursion.
Option 2: Calling the function twice or more is not necessary for recursion.
Option 3: Defining a variable outside does not affect recursion control.
Option 4: Correct. A base case ensures recursion eventually stops.
Correct Answer: Option 4 ✅
In Python, what happens if a recursive function does not have a base case?
In Python, if a recursive function lacks a base case, the function will keep calling itself without stopping. This creates an infinite recursion scenario. However, Python has a built-in recursion depth limit (default is 1000 calls).
Option 1: Incorrect, because the program cannot run indefinitely; Python will eventually throw an error.
Option 2: Incorrect, Python does not automatically fix the issue. It just raises an error when the limit is reached.
Option 3: Correct. Python raises a RecursionError: maximum recursion depth exceeded.
Option 4: Incorrect, since the function will not terminate after one call without a base case.
Correct Answer: Option 3 ✅
Which of the following is a valid recursive function definition in Python?
A valid recursive function in Python must:
Call itself inside the function body.
Include a base case to stop recursion.
Now let’s analyze the options:
Option 1: Invalid, because it has no base case, leading to infinite recursion.
Option 2: Incomplete, since it lacks a return value when x == 0.
Option 3: Correct. This is a classic factorial implementation using recursion, with a base case (x == 0).
Option 4: Not recursive at all, because the function does not call itself.
Correct Answer: Option 3 ✅
Which of the following functions correctly calculates the sum of all elements in a list using recursion?
This question tests writing a recursive function to sum elements in a list:
Option 1: Incorrect – Uses iteration, not recursion.
Option 2: Correct ✅ – Base case checks for an empty list, then adds the first element to the sum of the rest of the list recursively.
Option 3: Incorrect – Infinite recursion; no base case and no processing.
Option 4: Incorrect – Base case is invalid; lst == 0 will never be true for a list.
Key takeaway: For list recursion, always define a base case (empty list) and ensure the function reduces the list size on each recursive call.
Which of the following functions correctly returns the nth Fibonacci number using recursion?
This question tests the correct implementation of the Fibonacci sequence using recursion:
Option 2: Incorrect – Uses iteration, not recursion.
Option 3: Correct ✅ – Proper recursive definition: returns n for base cases (0 or 1) and adds the previous two Fibonacci numbers for others.
Option 4: Incorrect – Incorrect recursive formula; adds 1 instead of the previous Fibonacci number.
Key takeaway: For Fibonacci recursion, always define proper base cases (0 and 1) and reduce n in each recursive call to avoid infinite recursion.
Which of the following functions correctly finds the maximum element in a list using recursion?
This question tests finding the maximum value in a list using recursion:
Option 1: Correct ✅ – Base case: when list has one element, return it. Recursive step: find the maximum of the rest of the list and compare with the first element.
Option 2: Incorrect – Uses Python’s built-in max function, not recursion.
Option 3: Incorrect – Base case returns 0, does not compare elements, fails for negative numbers.
Option 4: Incorrect – Only returns the first element, ignoring the rest of the list.
Key takeaway: When using recursion for lists, define a base case for a single element, then combine results from recursive calls to solve the problem incrementally.
Which of the following functions correctly reverses a string using recursion?
This question tests using recursion to reverse a string:
Option 1: Incorrect – Uses slicing, not recursion.
Option 2: Correct ✅ – Base case: empty string returns "". Recursive step: reverse the substring excluding the first character and append the first character at the end.
Option 3: Incorrect – Prints characters in reverse but does not return the reversed string.
Option 4: Incorrect – Recursive step adds the first character at the start instead of the end, resulting in the original string.
Key takeaway: Recursive string reversal involves taking the first character, reversing the rest of the string recursively, and appending the first character at the end.
Which of the following functions correctly computes the GCD (Greatest Common Divisor) of two numbers using recursion?
This question tests using recursion to compute the GCD using the Euclidean algorithm:
Option 1: Correct ✅ – Base case: if b == 0, return a. Recursive step: call gcd(b, a % b).
Option 2: Incorrect – Uses iteration instead of recursion.
Option 3: Incorrect – Subtracts 1 from both numbers and may not find the correct GCD; also inefficient.
Option 4: Incorrect – Simply adds numbers; does not compute GCD.
Key takeaway: Recursive GCD relies on the Euclidean algorithm: keep replacing the pair with (b, a % b) until b is 0. The remaining a is the GCD.
Which of the following statements about recursive binary search is true?
This question tests understanding of the concepts behind recursive binary search:
Option 1: Incorrect – Binary search only works correctly on sorted lists.
Option 2: Incorrect – Base case is essential to stop recursion when the element is found or the search interval is empty.
Option 3: Incorrect – Binary search is faster than linear search for large sorted lists; its complexity is O(log n).
Option 4: Correct ✅ – Recursive binary search requires a sorted list and a base case to terminate the recursion.
Key takeaway: Recursive binary search relies on dividing the search interval in half, checking the middle element, and using a base case to terminate recursion either when the element is found or when the interval becomes empty.
Which of the following functions correctly checks if a string is a palindrome using recursion?
This question tests using recursion to check if a string is a palindrome:
Option 1: Incorrect – Uses slicing, not recursion.
Option 2: Correct ✅ – Base case: string of length 0 or 1 is a palindrome. Recursive step: check if first and last characters are equal and recurse on the substring excluding them.
Option 3: Incorrect – Uses iteration, not recursion.
Option 4: Incorrect – Does not perform any character checks, always returns True or False incorrectly.
Key takeaway: Recursive palindrome checking compares the first and last characters and reduces the problem size by slicing the string until the base case is reached.
Which of the following functions demonstrates multiple recursive calls correctly?
This question illustrates multiple recursive calls in a function:
Option 1: Incorrect – Returns n directly, no recursion.
Option 2: Correct ✅ – Each call to fib(n) makes two recursive calls: fib(n-1) and fib(n-2). This is a classic example of recursion with multiple recursive branches.
Option 3: Incorrect – Uses a loop instead of proper recursion to calculate Fibonacci.
Option 4: Incorrect – Recursive call fib(n) calls itself without reducing n, leading to infinite recursion.
Finally, all these return values are added together to compute fib(4) = 3.
Key takeaway: Multiple recursive calls occur when a function calls itself more than once in the same call. Understanding the call tree helps visualize how recursion works step by step.
Which of the following functions is an example of tail recursion?
This question explains tail recursion vs normal recursion:
Option 1: Incorrect – Normal recursion; the multiplication happens after the recursive call returns, so it is not tail recursion.
Option 2: Incorrect – Normal recursion with addition after returning from recursion; not tail recursion.
Option 3: Correct ✅ – Tail recursion; the recursive call is the last operation, and all necessary computation is passed through the accumulator acc.
Option 4: Incorrect – Fibonacci recursion involves multiple recursive calls and is not tail recursion.
Understanding Tail Recursion:
In tail recursion, the recursive call is the last operation of the function. This allows some languages to optimize recursion and reuse the same stack frame. Although Python does not optimize tail recursion, understanding the concept is important for algorithm design.
Key takeaway: Recursive functions can handle arbitrarily nested structures by checking the type of each element and recursing only when needed.
Which of the following statements correctly describes recursive backtracking?
This question tests understanding of recursion in backtracking algorithms:
Option 1: Incorrect – Recursive backtracking explores possibilities in a depth-first manner; it may not find the shortest path first.
Option 2: Incorrect – A base case is required to stop recursion at dead-ends or when the goal is reached.
Option 3: Correct ✅ – Recursive backtracking explores all possibilities. It goes deeper recursively, and when a path leads to a dead-end, it backtracks to try alternative paths.
Option 4: Incorrect – Backtracking is applicable to puzzles, strings, grids, and combinatorial problems, not just numbers.
Understanding recursive backtracking:
For example, navigating a maze:
1. Start at the entrance.
2. Move to a possible next step recursively.
3. If the path leads to a dead-end, return (backtrack) to the previous step and try another path.
4. Repeat until the exit is found or all paths are exhausted.
Key takeaway: Recursive backtracking is powerful for exploring all options systematically, using recursion to manage the current path and backtracking to previous states when needed.
Why is recursion often used in programming?
This question wraps up the key concept of recursion:
Option 1: Incorrect – Recursion is not always faster than iteration; sometimes it is slower due to function call overhead.
Option 2: Incorrect – Every recursive function requires a base case to terminate properly.
Option 3: Incorrect – Recursion can use extra memory due to the call stack, especially for deep recursion.
Option 4: Correct ✅ – Recursion is a natural fit for problems that can be divided into smaller sub-problems, such as factorials, Fibonacci numbers, tree traversal, and combinatorial problems.
Key takeaway: Recursion allows programmers to solve complex problems by defining a function in terms of itself. By focusing on smaller sub-problems and using base cases to terminate, recursion can simplify code readability and logic, especially for hierarchical or divide-and-conquer problems.
Quick Recap of Python Recursion Concepts
If you are not clear on the concepts of Recursion, you can quickly review them here before practicing the exercises. This recap highlights the essential points and logic to help you solve problems confidently.
What is Recursion in Python?
Recursion in Python is a technique where a function solves a problem by calling itself repeatedly. Instead of tackling the entire problem at once, recursion breaks it into smaller and more manageable sub-problems. Each recursive call processes a smaller portion of the task until a stopping condition — called the base case — is reached. Without this base case, the recursion would never end and would eventually crash the program.
How Recursion Works: Base Case and Recursive Case
Every recursive function is built around two core ideas:
Component
Meaning
Purpose
Base Case
A specific condition where recursion stops
Prevents infinite recursion
Recursive Case
Where the function calls itself with updated arguments
Gradually moves the function toward the base case
If both parts are not present — or if the function never gets closer to the base case — recursion becomes infinite.
Why Use Recursion Instead of Loops?
Loops and recursion can sometimes achieve the same results, but recursion is often chosen when a problem’s structure naturally repeats within itself. Recursion avoids complicated nested loops and uses the function call stack to handle repeated operations automatically.
This example demonstrates a function that counts down from a number to zero using recursion:
def countdown(n):
if n == 0:
print("Done!")
return
print(n)
countdown(n - 1)
Each call prints the current number and then calls itself with n - 1 until the base case n == 0 is reached.
Recursive Function with Return Value
Recursive functions can also return values that are combined as the recursion unwinds. Here is an example calculating factorial:
def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1)
Each call multiplies the result of the next recursive call, and once the base case is reached, all results are returned step by step to compute the final factorial value.
Common Use-Cases of Recursion
Recursion is widely used in programming for tasks that naturally break into smaller sub-problems. Some common use-cases include:
Calculating mathematical sequences like factorial and Fibonacci
Depth-First Search (DFS) in trees and graphs
Sorting algorithms such as quicksort and mergesort
Processing file systems and directory structures
Flattening or traversing nested lists or JSON/XML objects
These tasks are often more intuitive and easier to implement with recursion compared to loops.
Pitfalls of Recursion
While recursion is powerful, it must be used carefully. Common pitfalls include:
Missing base case, which leads to infinite recursion
Parameters not progressing toward the base case
Too many recursive calls can exceed Python’s recursion limit, causing a stack overflow
Execution may be slower than equivalent loops due to function call overhead
Always ensure that recursion moves toward a base case and is necessary for the problem at hand.
Best Practices for Writing Recursive Functions
Always define a clear, reachable base case to stop recursion
Ensure each recursive call progresses toward the base case
Validate input values before recursion starts to avoid errors
Convert to loops if recursion becomes too deep or inefficient
Use memoization or caching to optimize repeated calculations when needed
Test recursive functions with small inputs first to ensure correctness
Summary: Key Takeaways
Recursion is a function calling itself to solve smaller instances of a problem
Every recursive function requires both a base case and a recursive case
Ideal for hierarchical, branching, nested, and divide-and-conquer problems
Helps write cleaner, more intuitive code for tree/graph traversal and nested structures
Must be used carefully to avoid stack overflow and performance issues
Best practices include defining a clear base case, ensuring progress toward it, and using memoization when needed
Practicing Python Recursion? Don’t forget to test yourself later in our Python Quiz.
About This Exercise: Python Recursion Exercises
Welcome to Solviyo’s Python Recursion exercises, designed to help you master one of the most powerful concepts in Python programming. Recursion allows a function to call itself, enabling you to break down complex problems into smaller, manageable steps. These exercises guide you from basic recursion concepts to practical real-world applications.
What You Will Learn
In this set of Python Recursion exercises, you will explore:
Understanding the concept of recursion and how a function can call itself.
Writing basic recursive functions, such as calculating factorials and Fibonacci numbers.
Identifying and implementing base cases to prevent infinite recursion.
Solving problems that naturally fit recursion, such as traversing directories, nested lists, and tree structures.
Comparing recursion with iteration to determine the most efficient approach.
Applying recursion in real-world scenarios, including mathematical expressions and classic puzzles like the Tower of Hanoi.
Recognizing and avoiding common mistakes like infinite loops or stack overflow errors.
Why Learning Python Recursion Matters
Recursion is a fundamental tool in Python for solving problems that require repetitive, self-referential logic. Mastering recursion improves your problem-solving skills, allows you to write elegant and concise solutions, and prepares you for advanced topics such as algorithms, data structures, and functional programming.
Start Practicing Python Recursion Today
By completing these exercises, you will gain confidence in writing and applying recursive solutions to a variety of problems. Each exercise includes detailed explanations to reinforce learning and help you avoid common pitfalls. Start practicing Python Recursion exercises now and add this powerful tool to your Python programming toolkit.
Need a Quick Refresher?
Jump back to the Python Cheat Sheet to review concepts before solving more challenges.