Recursion
Recursion is a programming technique where a function calls itself in order to solve a problem.
The recursive approach breaks a problem down into smaller, more manageable sub-problems of the same type.
Components of Recursion:
Base Case:
The condition under which the recursion terminates.
It prevents infinite recursion by providing a simple, non-recursive solution to the smallest instance of the problem.
Recursive Case:
The part of the function where the function calls itself with a modified argument, gradually approaching the base case.
Types of Recursion:
Direct Recursion:
A function calls itself directly.
Indirect Recursion:
A function calls another function, which in turn calls the original function.
Example (Direct Recursion)
Factorial Function:
# base case
if number == 1 or number == 0:
return 1
else:
# Recursive case
return number*factorial(number–1)
Factorial of 5
print(f“factorial of 5 is : {fact}“)
Here, factorial(5) calls factorial(4), which calls factorial(3), and so on, until it reaches factorial(1).
Example (Indirect Recursion)
function_call_count = 0
def functionA():
# Telling function’s local space that i am using global variable.
global function_call_count
# Counting function call
function_call_count += 1
print(“Printing from functionA().“)
# Base case to break the function call otherwise it will go infinitely calling functions.
if function_call_count == 5:
return
# function call
functionB()
def functionB():
print(“Printing from functionB().“)
# Function call
functionA()
functionA()
Printing from functionB().
Printing from functionA().
Printing from functionB().
Printing from functionA().
Printing from functionB().
Printing from functionA().
Printing from functionB().
Printing from functionA().
Advantages of Recursion:
Simplifies the code for problems that can naturally be divided into similar sub-problems, like tree traversals, and certain mathematical computations (e.g., Fibonacci sequence).
Provides a clear and straightforward approach to solve problems like backtracking and divide-and-conquer algorithms.
Disadvantages of Recursion:
Can lead to high memory usage due to the depth of the call stack, especially if the recursion depth is large.
May result in slower performance compared to iterative solutions because of the overhead of multiple function calls.
Risk of stack overflow if the base case is not properly defined or if the problem size is too large.
Tail Recursion:
A special form of recursion where the recursive call is the last operation in the function.
Tail recursion can be optimized by the compiler to avoid increasing the call stack, converting the recursion into iteration internally.
Example
if number == 1 or number == 0:
return result
# Recursive case (only recursive case)
return tail_recursive_factorial(number–1, result*number)
tail_recursive_factorial(5)
Wall time: 0 ns
120
Conclusion
Recursion is a powerful tool in programming, enabling elegant solutions for complex problems by breaking them down into simpler sub-problems.
However, it requires careful implementation to manage memory and performance effectively.
