# 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.

Table of Contents

## 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.

Syntaxdef 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")

OutputValue 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`

Syntaxn! = 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)

OutputEnter 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))

OutputThe 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()

OutputTraceback (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))

Output120

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))

Output120

## 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!! *😊