Recursion : Python

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:

1. 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.

1. Recursive Case:
   • The part of the function where the function calls itself with a modified argument, gradually approaching the base case.

Types of Recursion:

1. Direct Recursion:

   • A function calls itself directly.

2. Indirect Recursion:

   • A function calls another function, which in turn calls the original function.

Example (Direct Recursion)

Factorial Function:

def factorial(number):
    # base case
    if number == 1 or number == 0:
        return 1
    else:
        # Recursive case
        return number*factorial(number-1)

Factorial of 5

fact = factorial(5)
print(f"factorial of 5 is : {fact}")

factorial of 5 is : 120

• Here, factorial(5) calls factorial(4), which calls factorial(3), and so on, until it reaches factorial(1).

Example (Indirect Recursion)

# variable to count how many times function called
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()

# Calling functionA()
functionA()

Printing from 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

def tail_recursive_factorial(number, result = 1):
    if number == 1 or number == 0:
        return result

    # Recursive case (only recursive case)
    return tail_recursive_factorial(number-1, result*number)

%%time
tail_recursive_factorial(5)

CPU times: total: 0 ns

Wall time: 0 ns

120

Most Important Python Does not optimize tail recursion. Some languages does not optimizes the tail recursion, and python is one of them.

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.

Comments

[Scott Reno]

Recursion can be good unless you can't stop. Recursion can be good unless you can't stop. Recursion can be good unless you can't stop. Recursion can be good unless you can't stop. Recursion can be good unless you can't stop. Recursion can be good unless you can't stop. Recursion can be good unless you can't stop. Recursion can be good unless you can't stop.

[Vincent A. Cicirello]

Python doesn't optimize tail recursion.

[Nitin Kendre]

yes, it is true. I am just learning the concepts. and I forgot to add it to the post. I will update you. It is best to use an iterative version in Python.

Thank you for noticing.😊