What is Recursive Function?
Function calls itself again and again till it satisfies a recursive condition. A recursion function breaks the problem down into smaller problems and calls its own logic to solve the smaller problem. This technique is known as divide and conquer. It’s used in mathematics and the computer science field.
The recursive function includes a base case (or terminal case) and a recursive case. In the base case, you can consider the major problem to solve and the recursive case divides the problem into smaller parts until it reaches a level where it can be solved readily. A recursive case may return a result or it may call itself again to further divide the problem. Each time the problem breaks down into smaller problem the function which is getting called recursively saves the state of the call and expect the result from itself after breaking down the problem.
Recursive Function in Python
The concept of recursion remains the same in Python. The function calls itself to breakdown the problem into smaller problems. The simplest example we could think of recursion would be finding the factorial of a number.
Let’s say we need to find the factorial of number 5 => 5! (Our problem)
To find 5! the problem can be broken into smaller ones 5! => 5 x 4!
So, to get 5! We need to find 4! and multiply it with 5.
4.8 (4,344 ratings)
Let’s keep on dividing the problem
5! = 4! x 5
4! = 3! x 4
3! = 3 x 2!
2! = 2 x 1!
1! = 1
When it reaches the smallest chunk i.e, getting the factorial of 1 we can return the result as
Let’s take a pseudo-code example:-
Algorithm for factorial
Let us see the algorithm for factorial:
function get_factorial( n ):
if n < 2:
return get_factorial(n -1)
Suppose we are finding a factorial of 5.
get_factorial(5) 5 * get_factorial(4) = returns 120 #1st call
get_factorial(4) 4 * get_factorial(3) = returns 24 #2nd call
get_factorial(3) 3 * get_factorial(2) = returns 6 #3rd call
get_factorial(2) 2 * get_factorial(1) = returns 2 #4th call
get_factorial(1) returns 1 #5th call
The end result will be 120 where we started the execution of the function. Our recursion function will stop when the number is so reduced that the result can be obtained.
- The first call which is getting the factorial of 5 will result in a recursive condition where it will be added to the stack and another call will be made after reducing the number to 4.
- This recursion will keep on calling and breaking the problem into smaller chunks until it reaches the base condition.
- The base condition here is when the number is 1.
- Every recursive function has its own recursive condition and a base condition.
Pros and Cons of Python Recursive Function
- The execution of recursion is so that it won’t do any calculations until reaches base condition.
- In reaching to base conditions you may run out of memory.
- In a large problem where there can be a million steps or we can say a million recursions to do the program might end up giving memory error or a segmentation fault.
- 1000000! = 1000000 * 999999 ! =?
- Recursion is different than iteration it doesn’t scale up like an iterative method.
- Different languages have different optimizations for recursion.
- In many languages, the iterative method would perform better than recursion.
- Every language has some restrictions over the depth of recursion which you might face when solving large problems.
- Sometimes it’s hard to understand the complex problems with recursion whereas it’s pretty simple with iteration.
- In some cases, recursion is a convenient and faster way to use.
- Very much useful in the traversal of the tree and binary search.
Python Code – Recursion vs Iteration
We understood what is recursion and how it works in Python, as we know all languages have different implementation of recursion for memory and computational optimizations. There can be a case where iteration would be faster than recursion.
Here we would compare both recursion and iteration method to see how Python performs in both the cases.
1. Recursion Code for Factorial
if n < 0:
elif n < 2: #base condition
return n * get_recursive_factorial(n -1) #recursion condition
2. Factorial problem using iteration (looping)
if n < 0:
fact = 1
for i in range( 1, n+1 ):
fact *= i
3. Printing Results
As we can see both give the same output as we have written the same logic. Here we can’t see any difference in execution.
Let’s add some time code to get more information about the execution of recursion and iteration in Python.
We will import the “time” library and check what time recursion and iteration take to return the result.
4. Code with time calculation
if n < 0:
elif n < 2:
return n * get_recursive_factorial(n-1)
if n < 0 :
fact = 1
for i in range(1, n+1):
fact *= i
start_time = time.time()
print("Recursion--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
print("Iteration--- %s seconds ---" % (time.time() - start_time))
We will do repeated executions with a different value for factorial and see the results. The below results could vary on machine to machine. We have used MacBook Pro 16 GB RAM i7.
We are using Python 3.7 for execution
Case 1:- Factorial of 6:
Case 2: Factorial of 50:
Case 3: Factorial of 100:
Case 4: Factorial of 500:
Case 5: Factorial of 1000:
We have analyzed both methods in a different problem. Moreover, both have performed similar except case 4.
In case 5 we got an error while doing it with recursion.
Python got a restriction on the maximum depth you can go with recursion but the same problem I was able to solve it with iteration.
Python has restrictions against the problem of overflow. Python is not optimized for tail recursion, and uncontrolled recursion causes a stack overflow.
“sys.getrecursionlimit()” function would tell you the limit for recursion.
The recursion limit can be changed but not recommended it could be dangerous.
Conclusion – Python Recursive Function
- Recursion is a handy solution for some problems like tree traversal and other problems.
- Python is not a functional programing language and we can see recursion stack is not that optimized as compared to iteration.
- We should use iteration in our algorithm as its more optimized in Python and gives you better speed.
This is a guide to Recursive Function in Python. Here we discuss What is Recursive Function, Recursive function in Python, Algorithm for factorial, etc. You can also go through our other suggested articles to learn more–