How to Create a Recursive Function in Python?

1. What is a recursive function in Python?

A function that calls itself is called a recursive function.

def recurse():
    ...
    recurse()
    ...

recurse()

Note: It is not possible to have an indefinite chain of function calls. To prevent infinite recursion, an if statement is typically used. That is, every recursive function must have a stopping condition to avoid infinite function calls.

The Python interpreter limits the recursion depths to prevent infinite recursion that can cause a stack overflow. By default, the maximum depth of recursion is 1000. If it exceeds the limit, it will result in a RecursionError. Example:

def recursor():
    recursor()
recursor()

Result

Traceback (most recent call last):
  File "c:\\python-examples\\sumPython.py", line 3, in <module>
    recursor()
  File "c:\\python-examples\\sumPython.py", line 2, in recursor
    recursor()
  File "c:\\python-examples\\sumPython.py", line 2, in recursor
    recursor()
  File "c:\\python-examples\\sumPython.py", line 2, in recursor
    recursor()
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Python program for calculating factorial using recursive function

Factorial of n is calculated as: S(n) = n! = 12…(n-1)n*

We see that S(n) = S(n-1)*n. Therefore, we will calculate S(n) instead of calculating S(n-1). Similarly, we calculate S(n-2), …, S(2), S(1), S(0) = 1.

#Factorial of n = 1*2*3*...*n
def factorial(n):
    if (n > 1):
        return n * factorial(n - 1)
    else:
        return 1

n = int(input("Enter a non-negative number: "))
while(n<=0):
    n = int(input("Enter a non-negative number: "))
result = factorial(n)
print("Factorial of", n, "=", result)

Result

Enter a non-negative number: 4
Factorial of 4 = 24

The function def factorial(n) is recursive and operates in the following way:

def factorial(n):
    if (n > 1):
        return n * factorial(n - 1)
    else:
        return 1

When the value of n is 4, the function factorial(n) is called, which means that the result = 4 * factorial(3). The function factorial(3) = 3 * factorial(2). The function factorial(2) = 2 * factorial(1). However, when n is 1 (which does not satisfy the condition if (n > 1)), return 1 is executed, which means factorial(1) = 1. Therefore, result = factorial(n) = 4*3*2*1 = 24.

2. Program to output Fibonacci sequence using recursive function

The Fibonacci sequence is a sequence of natural numbers that starts with 0 and 1, and each subsequent element is the sum of the two elements before it. The recursive formula for the fibonacci sequence is: f(n) = f(n-1) + f(n-2), with f(0) = 0, f(1) = 1.

To calculate f(n) for n > 1, we require the previous two Fibonacci numbers. The problem can be resolved using a recursive function, as demonstrated below:

def fibonacci(x):
    if x < 2:
        return x
    else:
        return fibonacci(x-1) + fibonacci(x-2)

i = 0
x = int(input("Enter the number of terms in the sequence: "))
while x < 1:
    x = int(input("Enter the number of terms in the sequence: "))

print("Fibonacci Series:")
while i < x:
    print(fibonacci(i), end=' ')
    i += 1

Result

Enter the number of terms in the sequence: 5
Fibonacci Series:
0 1 1 2 3

3. Advantages and disadvantages of recursive function

Advantages:

• It makes the code shorter and more straightforward.
• Solves complex tasks by breaking them down into simpler sub-problems.

Disadvantages:

• Continuous function calls can cause memory waste due to the initialization of local variables.
• Processing time is longer.
• Difficult to debug to find errors.