Recursion
- Understand how recursion works in Python with simple and practical examples.
What is Recursion?
Recursion is a programming technique where a function calls itself to solve a problem.
👉 A recursive function breaks a big problem into smaller sub-problems of the same type.
Why Do We Use Recursion?
Recursion is used when:
A problem can be divided into smaller parts
Repetition follows a clear pattern
Problem has a base condition
Code becomes simpler than loops
Real-Life Example:
Folder inside folder (directory structure)
Mathematical problems (factorial, Fibonacci)
Basic Requirements of Recursion
Every recursive function must have:
Base Condition – stops recursion
Recursive Call – function calling itself
⚠️ Without a base condition, recursion causes infinite calls.
Syntax of Recursion
def function_name():
if condition: # base condition
return value
else:
return function_name()
Basic Recursion Example
This function prints numbers from 1 to 5 using recursion.
def show(n):
if n > 5:
return
print(n)
show(n + 1)
show(1)
Factorial Using Recursion
This function calculates the factorial of a number using recursion.
def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1)
print(factorial(5))
Sum of Natural Numbers
This program calculates the sum of first n natural numbers.
def sum_numbers(n):
if n == 0:
return 0
return n + sum_numbers(n - 1)
print(sum_numbers(5))
When to Use Recursion?
Mathematical problems
Tree structures
Divide-and-conquer algorithms
Problems with repeated sub-structure
Advantages of Recursion
Simplifies complex problems
Cleaner and readable code
Useful for tree and graph problems
Disadvantages of Recursion
Uses more memory
Slower execution
Risk of stack overflow