Recursion is one of the fundamental concepts in computer science and is essential for programmers and data scientists alike. Not only are many sort and search algorithms recursive, but every Python interview will include some recursion-based questions. This marks recursion as a key concept to revise before any coding interview.
Today, we'll help you brush up on your recursive programming skills in Python and walk through 6 practice problems to get you hands-on experience.
Here’s what we’ll cover today:
- What is recursion?
- Recursion in Python
- Python recursion with numbers
- Python recursion with strings and arrays
- Python recursion with data structures
- What to learn next
Transition to Python in half the time
Brush up on the skills interviewers are looking for with dozens of hands-on practice problems.
Ace the Python Coding Interview
What is recursion?
Recursion is a concept in computer science when a function calls itself and loops until it reaches the desired end condition. It is derived from the mathematical concept of recursive definitions, which defines elements in a set in terms of other elements in the set.
Each recursive implementation has a base case, which is when the desired state has been reached, and a recursive case where the desired state has not been reached and the function enters another recursive step.
The behavior in the recursive case before the recursive function call, the internal self-call, is repeated on each step. Recursive structures are therefore useful when you can achieve a greater problem (the base case) by completing repeating subproblems (the recursive case) that incrementally move the program to the base case.
It results in similar behavior to for or while loops, except recursion progresses closer to a target condition, while for loops run a set number of times, and while loops run until a condition is no longer met.
In other words, recursion is declarative because you set the state you want to reach and for/while loops are iterative because you have to set the number of repetitions.
Take a look at the difference in syntax between iterative and recursive approaches:
Recursive
def RecursiveFunction() :
# Base Case
if <baseCaseCondition> : #sets target state
<return some base case value>
# Recursive Case
else :
<return(recursive call and any other task)>
for loop
arr = ["A", "B", "C"]
for x in arr: #sets the number of iterations
print(x)
while loop
i = 1
while i < 6: #sets number of iterations
print(i)
i += 1
Recursive solutions are best when a problem has clear subproblems that must be repeated and if you're unsure how many times you'd need to loop with an iterative solution.
For example, if you wanted to create a factorial function program that finds the factorial of an unknown number.
def factorial(n):
if n==0:
return 1
return n*factorial(n-1)
num = 5
print(factorial(num))
Direct vs Indirect Recursion
Thus far we've only discussed direct recursion, where the recursive function explicitly calls itself in its recursive step. There is also indirect recursion where the recursive call is removed from the function but still runs as a result of the original recursive step.
For example, functionA calls functionB, which then calls functionA again.
Direct
def function1(p1, p2, ..., pn) :
# Some code here
function1(p1, p2, ..., pn)
# Some code here
Indirect
def function1(p1, p2, ..., pn) :
# Some code here
function2(p1, p2, ..., pn)
# Some code here
def function2(p1, p2, ..., pn) :
# Some code here
function1(p1, p2, ..., pn)
# Some code here
Pros and cons of recursion in Python
All programming languages support recursion, however, not all are equally optimized.
Iteration is often preferred in Python and is regarded as more "pythonic" due to built-in optimizations. Generally, recursive solutions are preferred over iterative solutions on larger computations as recursion often results in less code and faster performance at scale.
Pros:
- Faster when optimized: If you include recursion optimizations like tail-end recursion and memoization, recursive approaches are faster in Python.
- Less code: Recursive solutions are more compact, which means you can write recursive solutions faster and have less code to review when debugging.
- Declarative: Many developers find the logic of declaring the desired state to be more understandable than iteration, which focuses on the steps needed to reach an unstated goal.
- Efficient Sort and Search: Recursion is especially useful for Python data science as it is the foundation of popular sort algorithms like mergesort.
Cons
-
Maximum recursion depth: Python has a limited call stack that supports only 1000 nested steps. While this may seem like a lot, it becomes an issue when dealing with large structures like lists and arrays. This can be overridden at your own rise with
sys.setrecursionlimit(1500). - Supported, not suggested: Python allows recursive calls but does not include many built-in optimizations. Unlike iterative optimizations, developers must code all-recursive improvements themselves.
- Uses more memory: Each call saves the previous step in the call stack until the recursive process is complete. This means recursive solutions use more memory than iterative ones.
I did not add readability to either column, as some developers find recursion easier to understand, while others find the nested behavior confusing. Ultimately, it's case-by-case per problem and developer.
Recursion in Python
Now, let's take a deeper look at recursive functions in Python.
Below is an example program that recursively prints the pattern: 10 5 0 5 10.
def printPattern(targetNumber) :
# Base Case
if (targetNumber <= 0) :
print(targetNumber)
return
# Recursive Case
print(targetNumber)
printPattern(targetNumber - 5)
print(targetNumber)
# Driver Program
n = 10
printPattern(n)
We want to print each number twice, except 0 that is only printed once in the middle. This lets us know that if (targetNumber <= 0) is our base case.
Our recursive case is therefore lines 7-9.
On line 8, you can see the recursive call, printPattern(targetNumber - 5), which moves our program into the next recursive step.
Line 9 prints the final 10 and is only run once as it is after the recursive call.
Remember, only behavior before the recursive call is repeated in the recursive loop.
Take a look at this program flowchart to see how the program steps connect:
Now that we've taken apart this recursive program, let's look at some applications of recursion.
Keep revising Python.
Recursion is a staple of any Python Coding Interview. Educative's hands-on, text-based courses let you transition to Python and land that next job fast.
Ace the Python Coding Interview
Python recursion with numbers
Fibonacci Sequence
First, we'll look at a classic recursion example: the Fibonacci sequence. This program takes a given number and returns its Fibonacci numbers.
def recur_fibo(n):
# Base Case
if n <= 1:
return n
else:
# Recursive Case
return(recur_fibo(n-1) + recur_fibo(n-2))
# Driver Code
num = 10
print (recur_fibo(num))
You can see our base case on line 2, if n >= 1. If this is not met, we move into the recursive case on line 5, which features two recursive calls.
Each time the loop recurses, n is lowered, meaning that our base case will eventually become true.
Sum from 1 to n
Now, we'll see how we can use recursion to sum all numbers from 1 to the given number. This program takes a positive integer as input and returns a single printout of the sum of all numbers between 1 and the integer.
def sumTill(targetNumber) :
# Base Case
if targetNumber == 1 :
return targetNumber
# Recursive Case
else :
return targetNumber + sumTill(targetNumber - 1)
# Driver Code
targetNumber = 5
print(sumTill(targetNumber))
Our program starts with the given number and adds the number one lower on each recursive step until it has reached 1.
The base case is on line 3, if targetNumber ==1. The recursive case adds the current value of targetNumber then calls sumTill() with a value lower by 1.
Python recursion with strings and arrays
Recursion is also helpful with strings or arrays. Many recursion interview questions will ask you to transform strings or arrays until all match certain criteria.
Remove spaces from a string
For this exercise, we'll create a program that takes a given string and returns a new string without any space or tab (/t) characters. For example, Hello World would become HelloWorld.
def remove(string):
# Base Case
if not string:
return ""
# Recursive Case
if string[0] == "\t" or string[0] == " ":
return remove(string[1:])
else:
return string[0] + remove(string[1:])
# Driver Code
print(remove("Hello\tWorld"))
Removing tabs from a null string "" will just return the null string "". Therefore, our base case will be when our original string is empty (line 3).
For the recursive case on lines 7 - 10, we check whether or not the current element is "\t" or " ":
- If the current element is
"\t"or" "we discard it and call another instance of the function after removing that element. - If the current element is not
"\t"or" ", we append it to the output string and call another instance of the function after removing that element.
Invert an Array
Now, we'll create a recursive program that takes a given array and returns the same array with elements in reverse order. For example, 1, 2, 3, 4 would become 4, 3, 2, 1.
def reverse(array):
# Base case1
if len(array) == 0: # If we encounter an empty array, simply return an empty array
return []
# Base case2
elif len(array) == 1 : # Inverting an array of size 1 returns the same array
return array
# Recursive case
return [array[len(array) - 1]] + reverse(array[:len(array) - 1])
# The first part is storing the last element to be appended later
# The second part is calling another instance of the same function with the last element removed
# Driver Code
array = [1, 2, 3, 4]
print(reverse(array))
For this solution, we'll make a temporary variable that saves the final element from the passed array on each recursive step. In the end, these values will be used to repopulate the array in reverse order because nested recursive functions complete deepest first.
The base cases of this problem are when the array has 0 or 1 element within because inverting these arrays will return the same array.
Python recursion with data structures
Finally, let's see how recursive functions can be used on data structures like linked lists and Binary Trees.
Reverse a Linked List
Reversing a linked list is similar to reversing an array, but is a bit more complicated. This program will accept a linked list and return the same linked list with nodes in the opposite order.
For example, the linked list 3, 4, 7, 11 would have a return value of 11, 7, 4, 3.
# main
import linkedList as l
def helperFunction(myLinkedList, current, previous) : # This function reverses the linked list recursively
# Base case
if current.next is None :
myLinkedList.head = current
current.next = previous
return
next = current.next
current.next = previous
# Recursive case
helperFunction(myLinkedList, next, current)
def reverse(myLinkedList):
# Check if the head node of the linked list is null or not
if myLinkedList.head is None:
return
# Call the helper function --> main recursive function
helperFunction(myLinkedList, myLinkedList.head, None)
# Driver Code
myLinkedList = l.LinkedList()
myLinkedList.append(3)
myLinkedList.append(4)
myLinkedList.append(7)
myLinkedList.append(11)
print("Original Linked List")
myLinkedList.printList()
reverse(myLinkedList)
print("\nReversed Linked List")
myLinkedList.printList()
# node.py
class Node:
def __init__(self, data):
self.data = data
self.next = None
# linkedList.py
import node as n
class LinkedList:
def __init__(self) :
self.head = None
def append(self, new_data):
new_node = n.Node(new_data)
if self.head is None : # If head node is null
self.head = new_node
return
last = self.head
while (last.next):
last = last.next
last.next = new_node # add new node to end of list
def printList(self):
temp = self.head
while(temp):
print(temp.data)
temp = temp.next
In the code snippet above, we pass our linked list, myLinkedList, to the function reverse(). This function checks whether or not the head of the linked list is null. If the head node is not null, we call the helperFunction(). This function is recursive and is where the reversal of the linked list takes place.
In the helperFunction(), the nodes are reversed using the following statements:
next = current.next # The original next node of the current node is saved
current.next = previous # The next of the current node is updated
After this change, we recursively call the function again:
# Recursive case
helperFunction(myLinkedList, next, current)
# The current node in the next recursive call will be the "next" node that we saved.
# The previous node will be the parent function's current node
The base case for this problem is where we reach the end of the linked list. This is where the next node of the current node will be None. We will make this last node the head of the linked list, update its position, and return.
Print all leaf nodes of a Binary Tree from left to right
This question is a bit tricky but is exactly the type of question you'll see in Python coding interviews.
We'll create a program that prints all leaf nodes as they appear from left to right on the tree diagram. This is the tree we'll be using.
The correct solution for this tree is 4 6 7 9 10.
Reminder: Leaf nodes are nodes that have no children and therefore end the subtree branch.
# Function to print leaf
# nodes from left to right
def printLeafNodes(root: Node) -> None:
# If node is null, return
if (not root):
return
# If node is leaf node,
# print its data
if (not root.left and
not root.right):
print(root.data,
end = " ")
return
# If left child exists,
# check for leaf recursively
if root.left:
printLeafNodes(root.left)
# If right child exists,
# check for leaf recursively
if root.right:
printLeafNodes(root.right)
# Driver Code
if __name__ == "__main__":
# Creates binary tree shown in
# above diagram
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.right.left = Node(5)
root.right.right = Node(8)
root.right.left.left = Node(6)
root.right.left.right = Node(7)
root.right.right.left = Node(9)
root.right.right.right = Node(10)
# print leaf nodes of the given tree
printLeafNodes(root)
# Binary tree node
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
This program takes the root node and prints all leaf nodes from left to right. Our base case is either 1) there are no remaining nodes, or 2) there are no remaining leaf nodes.
The program follows the connections of each child going left each time until it finds a leaf node. The program prints this value then repeats this subproblem along a different path of nodes.
Eventually, the function returns, and all leaf nodes will be printed from left to right.
What to learn next
Recursion is an essential part of any Python developer's skillset. Recursive questions often take up a large portion of interview questions at coding interviews and are essential for dynamic programming questions. The best way to learn these concepts is with hands-on experience with real interview questions.
Here are some questions to check out if you want to keep improving:
- 0-1 knapsack problem
- Balanced parentheses question
- Convert tree to a doubly linked list
- Reverse a stack
- Lowest common ancestor
You can find walkthroughs of these and more recursion interview questions in Educative's Ace the Python Coding Interview Path. This Path includes comprehensive practice and sample questions for top tested concepts like recursion, dynamic programming, concurrency, and OOP.
By the end, you'll be able to confidently walk into your next interview, knowing that you've practiced dozens of the most asked interview questions.
Top comments (0)