Kodeclik Blog

Recursion in Python

Recursion is a style of programming where a function calls itself one or more times repeatedly until a desired condition is met. Many classical algorithms in computer science are recursive in nature.

To understand recursion imagine we would like to write a function to print numbers from 1 to n. The usual, non-recursive, i.e., iterative way to write this function would be:

def printer(n):
for i in range(1,n+1):
  print(i)    
            
printer(10)

In recursion you would write it as:

def printer(n):
  if (n==1):
    print(n)
  else:
    printer(n-1)
    print(n)

printer(10)

Notice how in the definition of printer we call printer again! This is the essence of recursion, i.e. a function calling itself. Also note that when we call printer again recursively, we are calling it with a smaller argument, in this case (n-1). As recursive functions keep calling themselves, you need a base case to “stop” the recursion. That is taken care of by the “if” statement. In other words, the recursion stops when n reaches the value of 1.

To sum up the above function, if the input is 1, it just prints it and exits. If it is not 1, it calls it recursively with a smaller argument (n-1) and then prints (n). You can verify that it will print the same output as the non-recursive version.

What are other examples of recursion?

Suppose we would like to reverse a list. It is easy to write this recursively. As done above, given a list you need to think about how to call the function again with a smaller list. Here is one possible solution:

def reverse(x):
  if (x == []):
    # if list is empty
    # it is already reversed - return it!
    return(x)

  else:
    # get everything except the first element
    slist = x[1:]

    # reverse it
    reversed_slist = reverse(slist)

    # append the first element to the reversed list
    reversed_slist.append(x[0])

    # return this as the answer
    return(reversed_slist)

list = [1,2,3,4,5,6]
print(reverse(list))

This outputs:

[6, 5, 4, 3, 2, 1]

This program’s logic works as follows. Given a list, we take away the first element by indexing it only from “1” (which is the second element). We then reverse the list from this point and add back the first element but at the end of the list (not the front, from where we took it). This addition at the end is done via the append function.

There are many other common functions that can be implemented with recursion. The factorial is a popular example.

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

print(factorial(10))

This returns:

as expected.

Another example of recursion is the fibonacci function used to model growth of many natural phenomena:

def fib(n):
 if (n==0):
   return(0)
 elif (n==1):
   return(1)
 else:
   return(fib(n-1)+fib(n-2))
 
print(fib(6))

This produces:

as expected.

Note that in the above program each invocation of the function potentially results in two recursive calls, not one as in the earlier examples.

Is recursion better?

Recursion leads to simpler code and easier to understand code. But it is certainly a style of programming that might not be natural to many programmers.

When should I use recursion?

Recursion is natural for mathematical problems that are expressed in inductive notation and also for data structures like trees and graphs. In other words, the data structure itself is defined in a recursive manner and so traversing such data structures is naturally described using recursive notation.

What are the dangers with recursion?

Note that in all programs above there is a base case, i.e., the “if” case that is placed before the recursive call. If a suitable base case is not defined, the recursion will never stop and your program will run out of memory. For instance, let us try running the factorial program without the base case:

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

print(factorial(10))

When you run this program, even though it begins with a small number, i.e., 10, the recursive calls keep decreasing the argument indefinitely and you will get an error such as:

Traceback (most recent call last):
File "main.py", line 4, in <module>
  print(factorial(10))
File "main.py", line 2, in factorial
  return(n*factorial(n-1))
File "main.py", line 2, in factorial
  return(n*factorial(n-1))
File "main.py", line 2, in factorial
  return(n*factorial(n-1))
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

What this means is that the Python interpreter needs to book-keep and remember the original invocation to return to after each recursive call and after some point the interpreter runs of memory for such book-keeping. This is an example of bad programming practice.

How can I think recursively?

Recursion is just a programmatic way to express mathematical induction. If you can write functions by splitting them into a base case and an inductive step, you are well on your way to becoming a recursion expert!

Want to learn Python with us? Sign up for 1:1 or small group classes.