Loading notes...
Loading notes...
Class 12 • Chapter 4
Recursion involves a function calling itself to solve sub-problems, requiring a strict base case to prevent infinite memory usage.
Recursion is a programming technique where a function solves a problem by calling a smaller instance of itself. While it may seem counterintuitive at first, recursion is a fundamental tool in computer science used for solving tasks that have a repetitive, 'nested' structure—such as traversing tree-like data or implementing complex sorting algorithms. Instead of using traditional loops (Iteration), a recursive function breaks the problem down until it reaches a trivial state that can be solved directly, then 'unwinds' those solutions back to the original caller. This approach often results in code that is mathematically elegant, concise, and closer to a formal problem definition than its iterative equivalent.
Every time a function calls itself, Python creates a new 'Stack Frame' in the computer's memory. This frame stores the function's local variables and its current execution state. These frames are organized in a **Last-In, First-Out (LIFO)** data structure called the 'Call Stack.' As the recursion deepens, more frames are pushed onto the stack. Once the base case is reached, the functions begin returning results, and their frames are 'popped' off the stack one by one. This is why recursion can be memory-intensive; if a function calls itself too many times without reaching the base case, Python raises a 'RecursionError: maximum recursion depth exceeded'—a fail-safe mechanism to prevent your computer from crashing.
def factorial(n):
if n == 0 or n == 1: # Base Case
return 1
else: # Recursive Step
return n * factorial(n - 1)
print(factorial(5)) # Output: 120Recursion without a base case is like a loop without an exit condition—it will run 'infinitely' until it consumes all available memory. By default, Python limits the maximum recursion depth (usually around 1000 calls) to protect the system. You can check this limit using the sys.getrecursionlimit() function and even modify it if your application specifically requires deep recursion. However, a 'RecursionError' is almost always a sign of a missing base case or a logical flaw where the recursive step fails to move the input closer to the termination condition. Before writing recursive code, you must manually trace a simple case to ensure the logic eventually terminates.
# fib(n) = fib(n-1) + fib(n-2)
def fib(n):
if n <= 1: # Base Case
return n
return fib(n-1) + fib(n-2)
# Note: This version is slow for large n due to many repeated calls
print(fib(10)) # Output: 55Every recursive problem can be solved iteratively using loops, and vice-versa. So, why choose one over the other? **Recursion** is often cleaner for problems involving branching or hierarchical data (like searching through nested folders on a computer). However, **Iteration** is generally more memory-efficient and faster because it doesn't have the overhead of repeatedly creating and managing stack frames. Professional developers choose recursion when it makes the logic significantly easier to read and maintain, but they switch to iteration or 'tail-recursion' optimization when performance becomes a critical factor for large datasets.
def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1