Learn Python Recursion with Examples


1. Python Recursion

A few lessons back, we introduced you to Functions in Python. In that, we saw how to define our own functions, how to call them, and also learned some in-built functions. The last topic we discussed in brief was recursion in python. In this python tutorial, we will expand python recursion with syntax and examples for better understanding.

Recursion in Python

2. Introduction to Recursion in Python

According to the Oxford English Dictionary, recursion is the repeated application of a recursive procedure or definition.

Do you see the recursion in this definition itself? They used the word ‘recursive’ to define ‘recursion’. We sense an Easter egg here. Anyway, so as we talk about recursion, we’ll take the coolest example first. Take a look at the logo for PyPy, an implementation of Python with a Just-In-Time Compiler.

python recursive function

Python Recursion – pypy

The snake biting its own tail, feeding itself, is an example of recursion we’d like to give to you.

To take a more general example, when our anxiety creates more anxiety for us, it is recursion.

In programming, recursion is when a function calls itself. We’ll see this in detail in the following sections of recursion in Python Example.

3. Example of Recursive Function Python

We know that in Python, a function can call another. But when it calls itself, there must be a base condition, along with a decrement statement, to avoid an infinite loop. For this, we’ll take a python recursive  function example to calculate a number’s Python recursion factorial, since it’s the Hello World for recursion. The factorial of a number n is n*(n-1)*(n-2)*..*2*1. So, 5! = 5*4*3*2*1. Let us see how to write a recursive function.

First, let’s do it without recursion.

>>> def factorial(n):
f=1
while n>0:
f*=n
n-=1
print(f)
>>> factorial(4)

24

>>> factorial(5)

120

Now, let’s implement this with recursion. We mean to make factorial() call factorial().

>>> def factorial(n):
if n==1:
return 1
return n*factorial(n-1)
>>> factorial(5)

120

>>> factorial(4)

24

See how easy that was?

Read: Python Applications – 9 Real World Applications of Python Programming

a. Working of Python Recursion

To be clearer, we’ll explain how this works.

Our factorial() function takes n as argument. The base case that it defines to get out of the Python recursion is when n is equal to 1. In that case, the function will return 1.

Otherwise, it will return n multiplied by factorial(n-1). This is a recursive call to itself. So this is how it goes:

factorial(5)

=5*factorial(4)

=5*4*factorial(3)

=5*4*3*factorial(2)

=5*4*3*2*factorial(1)

=5*4*3*2*1

=5*4*3*2

=5*4*6

=5*24

=120

Hence, we get 120 as the output for factorial(5).

b. RecursionError in Python

So far, the code seems to work fine. But now, let’s try passing -2 as an argument to this.

>>> factorial(-2)
Traceback (most recent call last):
File "<pyshell#262>", line 1, in <module>
factorial(-2)
File "<pyshell#259>", line 4, in factorial
return n*factorial(n-1)
File "<pyshell#259>", line 4, in factorial
return n*factorial(n-1)
File "<pyshell#259>", line 4, in factorial
return n*factorial(n-1)
[Previous line repeated 989 more times]
File "<pyshell#259>", line 2, in factorial
if n==1:

RecursionError: maximum recursion depth exceeded in comparison

Add this one to the list of exceptions in our tutorial on Python Errors and Exceptions.Also Read our article on Exception Handling in Python for Python Programming

4. Advantages of Recursion in Python

With Python recursion, there are some benefits we observe:

  1. A recursive code has cleaner-looking code.
  2. Recursion makes it easier to code, as it breaks a task into smaller ones.
  3. It is easier to generate a sequence using recursion than by using nested iteration.

5. Disadvantages of Recursion in Python

The flip side of the coin is easy to quote:

  1. Although it makes code look cleaner, it may sometimes be hard to follow.
  2. They may be simpler, but recursive calls are expensive. They take up a lot of memory and time.
  3. Finally, it isn’t as easy to debug a recursive function.

6. More Examples of Python Recursion Function

Before we leave for today, we’ll take a couple more examples to understand Python Recursion better.

First, let’s define a function to calculate the sum of the first n natural numbers.

>>> def sumofn(n):
if n==1:
return 1
return n+sumofn(n-1)
>>> sumofn(16)

136

Here, sumofn(16)= 16+sumofn(15)

=16+15+sumofn(14)

=16+120

=136

Let’s take just one more example before we say goodbye. In this one, we’ll store the first n terms from the Fibonacci series for argument ‘n’.

>>> a,b,fib=0,1,[]
>>> fib.append(a)
>>> fib.append(b)
>>> def fibonacci(n):
if n==2:
return
global a,b
a,b=b,a+b
fib.append(b)
fibonacci(n-1)
>>> fib

[0, 1]

>>> fibonacci(9)
>>> fib

[0, 1, 1, 2, 3, 5, 8, 13, 21]

Honestly, we had fun coding this one. What we do here is, first, we store the values 0 and 1 in variables a and b. We also declare an empty list ‘fib’. Then, we append a and b to fib (for 0 and 1). It is now that we define the recursive function for our purpose.

In our base case, we check for n==2, because we already added two terms to the list. When n is 2, we ‘return’ (our work is done here). Then we use the global keyword for a and b to be able to access them.

Our main logic is in the line a,b=b,a+b. With this, we give b’s value to a, while simultaneously adding both values and giving the sum to b. Then we append b’s value to fib, and then call the function for one less term.

Finally, we call the function on the value 9 to get 9 terms in the list fib. Wasn’t this interesting? Would you like to add some more examples?

Read: Advantages and Disadvantages of Python Programming Language

7. Conclusion

In this entire article, we’ve focused on recursion in python and its examples. Repeating it, recursion is when you use something to define itself. Next, we saw its advantages and disadvantages. While it is expensive, it also leads to cleaner code. Keep doing some recursion Python Practice and exercises.