Recursion in Python

In this Python article, we will discuss how to create a recursive function and how does recursion works in python with some examples.

1. How does Recursion work in python?

Recursion can be defined as an operation performed multiple times with different inputs. A recursive function can be understood as a function that calls itself.

Python supports the recursion of function, as we know that a function can call another function. In the same way, a function can call itself as many numbers of time with different inputs forming a recursion function.

Recursion is generally regarded as a mathematical and programming concept. The recursive function must have a base condition as it is quite easy to write a never-terminating function if there is no condition to stop. So it is very important to have a condition that can stop the recursion.

Recursion is very effective and this mathematical approach of programming tries to run the function again and again with different inputs.

Recursion works with the help of a stack, it puts the function called in a stack until the last recursive function, once the work is done, the functions are removed from the stack one by one.

Syntax

def recursive_function(parameter):  #function is defined
  statements
  if (base condition):
    return some_value
  recursive_function(modified parameters)  #recursive call
...
recursive_function(parameter) #First call of the function 

Recursive functions are easy to implement and the best way to find correctness is by testing and modifying them. Let’s take some examples to understand recursion better.

1.1. Binary search using recursion

We can implement a binary search program with the help of a recursion function.

# Binary search in Python by recursion
def binarysearch(arr, start, end, x):
  if end >= start:   # base condition
    mid = (start + end) // 2
    if arr[mid] == x:   # If value found at the mid
      return mid
    elif arr[mid] > x:   # If value is smaller than mid
      return binarysearch(arr, start, mid-1, x)
    else:
      return binarysearch(arr, mid+1, end, x)
  else:
    return 0   # Value not found


arr = [1, 3, 5, 9, 12, 17, 19]
x = 17

# Function call
result = binarysearch(arr, 0, len(arr)-1, x)
if result != 0:
  print("Value found at index", str(result))
else:
  print("Value not found in array")
Output
Value found at index 5

1.2. Find Factorial using recursion

Factorial of a number n is a product of all numbers(integers) from 1 to n. It means that factorial of 5 (denoted by 5!) is 5*4*3*2*1=120

Syntax

n! = n x (n−1)! 
n! = n x (n−1) x (n−2)!
n! = n x (n−1) x (n−2) x (n−3)!
⋅ ⋅ 
n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2 x 1!    #1!=1     
# Factorial of any number
def factorial(x):
  if x == 1:
    return 1  # base condition to stop the iteration
  else:
    return (x * factorial(x-1))  # recursive call


x = int(input("Enter the number "))
print("Factorial is ", factorial(x)
Output
Enter the number 5
Factorial is 120

The factorial of the number is calculated by multiplying it until the number is equal to one. This recursive call can be explained in the following steps.

factorial(5)                 # 1st function call 5
5 * factorial(4)             # 2nd function call 4
5 * 4 * factorial(3)         # 3rd function call 3
5 * 4 * 3 * factorial(2)     # 4th function call 2
5 * 4 * 3 * 2 * factorial(1) # 5th function call 1
5 * 4 * 3 * 2 * 1            # return 5th call as x=1
5 * 4 * 3 * 2                # return from 4th call
5 * 4 * 6                    # return from 3rd call
5 * 24                       # return from 2nd call
120                          # return from 1st call

1.3. Print Fibonacci series using recursion

Let’s implement the program to print Fibonacci series using recursion.

# Fibonacci Series
def fibonacci_series(x):
  if x <= 1:  # base condition
    return x
  else:
    return(fibonacci_series(x-1) + fibonacci_series(x-2))


total_terms = 7

if total_terms <= 0:  # Fibonacci series term cannot be less than 1
  print("Input Invalid ! Give some positive input")
else:
  print("The series formed is:")
  for i in range(total_terms):
    print(fibonacci_series(i))
Output
The series formed is:
0
1
1
2
3
5
8

The Python interpreter has a limit to the depths to call the recursion function to avoid infinite recursions which results in a stack overflow error.

By default, there is a maximum depth of recursion which is set to 1000. If the program or the recursive function crosses the limit then the results in RecursionError. Let’s look at one such condition with the help of a small example.

Note: We can also update this limit if we want and this is the default limit.

def recur():
  recur()  #no base condition
recur()
Output
Traceback (most recent call last):
   File "", line 1, in 
   File "", line 2, in recur
   File "", line 2, in recur
   File "", line 2, in recur
   [Previous line repeated 996 more times]
 RecursionError: maximum recursion depth exceeded                      

2. Advantages of recursion

  • Recursion splits a complex problem function into simpler and smaller sub-problems.
  • The code looks simpler and easier to understand.
  • It is better to use recursion for sequence creation rather than iteration.

3. Disadvantages of recursion

  • It takes too much space and time which can be expensive for the user.
  • Debugging the recursive functions is not easy.
  • It is sometimes hard to follow through with the logic behind the recursion.

4. What is Tail Recursion

Tail-recursion can be defined as a special kind of recursion in which the last statement of a function is a recursive call. This recursion may be automated which means instead of generating a new stack frame, the output will be returned in the current stack which is performing the request.

The compiler makes tail-recursion optimized which becomes better than non-tail recursive functions.

Can the use of a tail-recursive function make it possible to optimize a program over a non-tail-recursive function?
Let’s take an example to understand this concept easily. The example below has the function to calculate the factorial of a number n. If we focus, we can clearly factorial(x) use the output of factorial(x-1).

So we can say that the call to factorial(x-1) is not the last thing done by factorial(x) which means that the function looks like a tail-recursive but it is a non-tail-recursive function.

# non-tail recursive factorial function
def factorial(x):
  if (x == 0):  # base condition
    return 1
  return x * factorial(x-1)


print(factorial(5))
Output
120

We can make the function factorial into a tail-recursive function. To do so we have to pass one more argument which will accommodate the factorial value. When x will reach 0, it returns the final value of the factorial of the desired number.

# A tail recursive factorial function
def factorial(x, y=1):
  if (x == 0):  # base condition
    return y
  return factorial(x - 1, x * y)


print(factorial(5))
Output
120

5. Conclusion

In this article we learned about

  • What is recursion with some examples and its advantages and disadvantages
  • What is Tail recursion with an example

Complete code samples are present on Github project.

An investment in knowledge always pays the best interest. I hope you like the tutorial. Do come back for more because learning paves way for a better understanding

Do not forget to share and Subscribe.

Happy coding!! 😊

Recommended -

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x