# How to Create a Recursive Function in Python?

This post is lesson 17 of 54 in the subject Python Programming Language

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