Recursion

Recursion: Introduction

Recursion is a technique for solving problems by breaking a problem down into smaller and smaller subproblems until the subproblems are small enough to be solved directly. A recursive algorithm is one that calls itself until it reaches a base case. The case that needs to call itself is called the recursive case. The base case is the case that is solved directly.

Call Stack

Call stack is a stack that keeps track of the function calls that are currently being made.

def funcThree():
    print('Three')

def funcTwo():
    funcThree()
    print('Two')

def funcOne():
    funcTwo()
    print('One')

funcOne()

In the above example, funcOne() calls funcTwo and funcTwo() calls funcThree(). Therefore, funcThree() is on the top of the call stack, then funcTwo() is on the second position, and funcOne() is on the third position. After funcThree() is called, it will be popped off the call stack and so on, until funcOne() is called. We can use the debug tool to see the call stack.

Factorial

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5))

The factorial of a number is the product of all the numbers from 1 to that number. For example, the factorial of 5 is 5 * 4 * 3 * 2 * 1 = 120. It is a example of a recursive function. In the call stack, the factorial of 5 is on the bottom of the call stack, and the factorial of 1 is on the top.