Recursion

Base case & general case

• Recursion is a process using a function or procedure that is defined in terms of itself and calls itself.

• The process is defined using a base case, a terminating solution to a process that is not recursive, and a general case, a solution to a process that is recursively defined.

def factorial(n):
    if n= 1:
        return 1 #base case
    return n * factorial(n-1) #general case

n = int(input())
result = factorial(n)
print(result)

Winding & unwinding

• With recursive functions, the statements after the recursive function call are not executed until the base case is reached; this is called winding.

• After the base case is reached and can be used in the recursive process, the function is unwinding.

Benefits of recursion

• Recursive solutions can contain fewer programming statements than an iterative solution.

• The solutions can solve complex problems in a simpler way than an iterative solution.

• However, if recursive calls to procedures and functions are very repetitive, there is a very heavy use of the stack, which can lead to stack overflow.

• For example, factorial(100) would require 100 function calls to be placed on the stack before the function unwinds.

How a compiler implements recursion

• Recursive code needs to make use of the stack; therefore, in order to implement recursive procedures and functions in a high-level programming language, a compiler must produce object code that pushes return addresses and values of local variables onto the stack with each recursive call, winding.

• The object code then pops the return addresses and values of local variables off the stack, unwinding.

def fib(n):
    if n <= 2:
        return 1 #base case
    return fib(n-1) + fib(n-2) #general case