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
def recursor(): recursor() recursor()
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)
Enter a non-negative number: 4 Factorial of 4 = 24
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
Enter the number of terms in the sequence: 5 Fibonacci Series: 0 1 1 2 3
3. Advantages and disadvantages of recursive function
- It makes the code shorter and more straightforward.
- Solves complex tasks by breaking them down into simpler sub-problems.
- Continuous function calls can cause memory waste due to the initialization of local variables.
- Processing time is longer.
- Difficult to debug to find errors.