Recursion in Python
Recursion means that a function calls itself during its execution. It is used to solve problems that can be broken down into smaller, similar problems.
Every recursive function must have:
- Base Case: A condition to stop the recursion.
- Recursive Case: The part where the function calls itself.
Syntax:
def function_name():
if condition:
return value # base case
else:
return function_name() # recursive callExample: Find factorial using recursion
def factorial(n):
if n==0 or n == 1:
return 1
else:
return n * factorial(n - 1)
print("Factorial of 5 is:", factorial(5))Output:
Factorial of 5 is: 120
Explanation:
factorial(5)callsfactorial(4), which callsfactorial(3), and so on.- When
n == 1, it returns 1 (base case). - The results are multiplied as the function returns back step-by-step.
- So,
5×4×3×2×1 = 120.
Fibonacci Series using Recursion
The Fibonacci Series is a sequence where each number is the sum of the two previous
numbers.
It starts with 0 and 1.
Formula: F(n) = F(n-1) + F(n-2)
Example Sequence: 0, 1, 1, 2, 3, 5, 8, 13, ...
Syntax:
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)Example: Print first 6 terms
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
print("Fibonacci series:")
for i in range(6):
print(fibonacci(i))Output:
Fibonacci series:
0
1
1
2
3
5
Explanation:
fibonacci(0)returns 0fibonacci(1)returns 1- Next terms:
1 (0+1),2 (1+1),3 (1+2),5 (2+3) - Each function call makes two smaller recursive calls until
n <= 1.
Key Points to Remember:
- Recursion is used when a task can be divided into similar smaller tasks.
- It must always have a base case, otherwise it may go into infinite calls and crash.
- Recursion is useful for problems like factorial, Fibonacci, tower of Hanoi, etc.
- It can sometimes be less efficient than loops if not used properly.