Home/Blog/Programming/Recursion in Python Tutorial
Home/Blog/Programming/Recursion in Python Tutorial

Recursion in Python Tutorial

Ryan Thelin
Feb 03, 2021
10 min read

Become a Software Engineer in Months, Not Years

From your first line of code, to your first day on the job — Educative has you covered. Join 2M+ developers learning in-demand programming skills.

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:


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:

def RecursiveFunction() :
  # Base Case
  if <baseCaseCondition> : #sets target state
    <return some base case value>
 
  # Recursive Case
  else :
    <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 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.

def function1(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 withsys.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:

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

1 of 4

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.py
node.py
linkedList.py
# 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.


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.

%0 node_1 1 node_2 2 node_1->node_2 node_3 3 node_1->node_3 node_1612399944016 4 node_2->node_1612399944016 node_1612399929097 5 node_3->node_1612399929097 node_1612399921241 8 node_3->node_1612399921241 node_1612399922865 6 node_1612399929097->node_1612399922865 node_1612399955316 7 node_1612399929097->node_1612399955316 node_1612399961675 9 node_1612399921241->node_1612399961675 node_1612399954258 10 node_1612399921241->node_1612399954258

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


Continue reading about Python and recursion#

  

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

TRENDING TOPICS

Learn to Code

Tech Interview Prep

Generative AI

Data Science

Machine Learning

GitHub Students Scholarship

Early Access Courses

Blind 75

Pricing

For Individuals

Try for Free

Gift a Subscription

CONTRIBUTE

Become an Author

Become an Affiliate

Earn Referral Credits

RESOURCES

Blog

Cheatsheets

Webinars

Answers

ABOUT US

Our Team

Careers

Hiring

Frequently Asked Questions

Contact Us

Press

LEGAL

Privacy Policy

Cookie Policy

Terms of Service

Business Terms of Service

Data Processing Agreement

INTERVIEW PREP COURSES

Grokking the Modern System Design Interview

Grokking the Product Architecture Design Interview

Grokking the Coding Interview Patterns

Machine Learning System Design

Tiktok Streamline Icon: https://streamlinehq.com

Copyright ©2024 Educative, Inc. All rights reserved.

soc2