Recursive Function in Python

What is Recursive Function?

Recursive Function in Python is used for repetitively calling the same function until the loop reaches the desired value during the program execution by using the divide and conquer logic. One of the obvious disadvantages of using a recursive function in the Python program is ‘if the recurrence is not a controlled flow, it might lead to consumption of a solid portion of system memory. For rectifying this problem, an incremental conditional loop can be used in place of the Recursive function in a python programming language.

Recursive Function in Python

The concept of recursion remains the same in Python. The function calls itself to break down 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.

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 1
    else:
      return get_factorial(n -1)

Function calls

Suppose we are finding 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 it reaches the base condition.
• In reaching to base conditions, you may run out of memory.
• There can be a million steps in a large problem, 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 from 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.

Some Pros

• In some cases, recursion is a convenient and faster way to use it.
• Very much useful in the traversal of the tree and binary search.

Python Code – Recursion vs Iteration

We understood what recursion is and how it works in Python, as we know all languages have different implementations 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 methods to see how Python performs in both cases.

1. Recursion Code for Factorial

def get_recursive_factorial(n):
    if n < 0:
        return -1
    elif n < 2:                                     #base condition
        return 1
    else:
        return n * get_recursive_factorial(n -1)    #recursion condition

2. Factorial problem using iteration (looping)

def get_iterative_factorial(n):
    if n < 0:
        return -1
    else:
        fact = 1
        for i in range( 1, n+1 ):
            fact *= i
        return fact

3. Printing Results

print(get_recursive_factorial(6))
print(get_iterative_factorial(6))

Output:

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

import time
def get_recursive_factorial(n):
    if n < 0:
        return -1
    elif n < 2:
        return 1
    else:
        return n * get_recursive_factorial(n-1)
def get_iterative_factorial(n):
    if n < 0 :
        return -1
    else:
        fact = 1
        for i in range(1, n+1): 
            fact *= i
        return fact
start_time = time.time()
get_recursive_factorial(100)
print("Recursion--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
get_iterative_factorial(100)
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 from machine to machine. We have used MacBook Pro 16 GB RAM i7.

We are using Python 3.7 for the 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 could solve 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 it’s more optimized in Python and gives you better speed.

Recommended Articles

This is a guide to the Recursive Function in Python. Here we discuss What is Recursive Function, a Recursive function in Python, Algorithm for factorial, etc. You can also go through our other suggested articles to learn more–

1. Factorial in Python
2. Spark Shell Commands
3. Finally in Python
4. Lambda in Python