Learn Python Recursion Function – Example, Pros and Cons
Master Python with 70+ Hands-on Projects and Get Job-ready - Learn Python
A few lessons back, we introduced you to Functions in Python, in which we studied Python Recursion Function. Here, in this Python Recursion tutorial, we discuss working an example of recursion function in Python.
Along with this, we will learn pros and cons of Python Recursion Function.
So, let’s start the Python Recursion Function Tutorial.
What is Recursion Function 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.
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.
Example of Python Recursive Function
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 Python recursion function.
>>> def factorial(n): f=1 while n>0: f*=n n-=1 print(f) >>> factorial(4)
Output
>>> factorial(5)
Output
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)
Output
>>> factorial(4)
Output
See how easy that was?
1. How Python Recursion Function Works?
To be clearer, we’ll explain how recursion function works in Python.
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).
2. 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)
Output
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)
[The 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
Python Recursion Function – Pros & Cons
1. Python Recursion Function Advantages
With Python recursion, there are some benefits we observe:
- A recursive code has a cleaner-looking code.
- Recursion makes it easier to code, as it breaks a task into smaller ones.
- It is easier to generate a sequence using recursion than by using nested iteration.
2. Python Recursion Function Disadvantages
The flip side of the coin is easy to quote:
- Although it makes code look cleaner, it may sometimes be hard to follow.
- They may be simpler, but recursive calls are expensive. They take up a lot of memory and time.
- Finally, it isn’t as easy to debug a recursive function.
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)
Output
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
Output
>>> fibonacci(9) >>> fib
Output
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
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
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?
So, this was all about Python Recursion Function Tutorial. Hope you like our explanation.
Python Interview Questions on Recursive Function
- What is a recursive function in Python?
- What is recursion in Python? Explain with an example.
- How does recursive function work in Python?
- How do you read recursion in Python?
- What is the use of recursion function in Python?
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.
Did we exceed your expectations?
If Yes, share your valuable feedback on Google