What is recursion?

Recursion is a programming approach where a function calls itself to solve a problem.

Key features:

• Base case: The exit condition for recursive calls. Without it, recursion leads to infinite loops.
• Recursive case: The condition where the function calls itself with modified arguments approaching the base case.

Advantages:

• More elegant and understandable for problems with natural recursive structure (e.g., tree traversal, factorial calculation).

Disadvantages:

• Can cause stack overflow with deep recursion.
• Often less efficient in memory and time compared to iterative solutions.

Example of factorial calculation:

def factorial(n):
    # Base case: factorial of 0 or 1 is 1
    if n == 0 or n == 1:
        return 1
    # Recursive case: n * factorial of n-1
    else:
        return n * factorial(n-1)

print(factorial(5)) # Outputs 120