Feb 03, 2021 - 10 min read

Ryan Thelin

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

Brush up on the skills interviewers are looking for with dozens of hands-on practice problems.

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:

def RecursiveFunction() :# Base Caseif <baseCaseCondition> : #sets target state<return some base case value># Recursive Caseelse :<return(recursive call and any other task)>

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 1return n*factorial(n-1)num = 5print(factorial(num))

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.

def function1(p1, p2, ..., pn) :# Some code herefunction1(p1, p2, ..., pn)# Some code here

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.

def printPattern(targetNumber) :# Base Caseif (targetNumber <= 0) :print(targetNumber)return# Recursive Caseprint(targetNumber)printPattern(targetNumber - 5)print(targetNumber)# Driver Programn = 10printPattern(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:

Let’s watch the call stack as this program steps through:

Now that we’ve taken apart this recursive program, let’s look at some applications of recursion.

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.

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 Caseif n <= 1:return nelse:# Recursive Casereturn(recur_fibo(n-1) + recur_fibo(n-2))# Driver Codenum = 10print (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.

`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 Caseif targetNumber == 1 :return targetNumber# Recursive Caseelse :return targetNumber + sumTill(targetNumber - 1)# Driver CodetargetNumber = 5print(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.

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.

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 Caseif not string:return ""# Recursive Caseif string[0] == "\t" or string[0] == " ":return remove(string[1:])else:return string[0] + remove(string[1:])# Driver Codeprint(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.

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 case1if len(array) == 0: # If we encounter an empty array, simply return an empty arrayreturn []# Base case2elif len(array) == 1 : # Inverting an array of size 1 returns the same arrayreturn array# Recursive casereturn [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 Codearray = [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.

Finally, let’s see how recursive functions can be used on data structures like linked lists and Binary Trees.

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.py

node.py

linkedList.py

# linkedList.pyimport node as nclass LinkedList:def __init__(self) :self.head = Nonedef append(self, new_data):new_node = n.Node(new_data)if self.head is None : # If head node is nullself.head = new_nodereturnlast = self.headwhile (last.next):last = last.nextlast.next = new_node # add new node to end of listdef printList(self):temp = self.headwhile(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`

.

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.

main.py

node.py

# Binary tree nodeclass Node:def __init__(self, data):self.data = dataself.left = Noneself.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.

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.

WRITTEN BYRyan Thelin

Join a community of more than 1.6 million readers. A free, bi-monthly email with a roundup of Educative's top articles and coding tips.