Recursion
Recursion is a technique where a function calls itself to solve smaller instances of the same problem. It's especially useful for tasks that have a recursive structure (like tree traversal, factorial, Fibonacci).
Example: Factorial
Base case: factorial(0) = 1. Recursive case: n! = n * (n-1)!
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print(factorial(5)) # 120
Example: Fibonacci
Base cases: fib(0)=0, fib(1)=1. Recursive case: fib(n)=fib(n-1)+fib(n-2).
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(6)) # 8
Important Considerations
- Always have a base case to stop recursion.
- Recursion can be memory‑intensive due to call stack.
- For deep recursion, Python's recursion limit may be reached; use iteration or increase limit with `sys.setrecursionlimit()`.
Two Minute Drill
- Recursion solves problems by breaking them into smaller subproblems.
- A recursive function must have a base case and a recursive case.
- Useful for tree traversal, divide‑and‑conquer, backtracking.
- Potential stack overflow for very deep recursion; consider iteration when needed.
Need more clarification?
Drop us an email at career@quipoinfotech.com