Recursion — Think Like a Computer

def countdown(n):
    if n <= 0:        # base case
        print("Done!")
        return
    print(n)
    countdown(n - 1)  # recursive case

def factorial(n):
    if n == 0: return 1        # base case
    return n * factorial(n-1)  # recursive case
 
factorial(3)
# = 3 * factorial(2)
# = 3 * 2 * factorial(1)
# = 3 * 2 * 1 * factorial(0)
# = 3 * 2 * 1 * 1 = 6

def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

def fib(n, memo={}):
    if n in memo: return memo[n]
    if n <= 1: return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # sort left half
    right = merge_sort(arr[mid:])  # sort right half
    return merge(left, right)      # combine

def inorder(node):
    if not node: return    # base case
    inorder(node.left)     # left subtree
    print(node.val)        # process
    inorder(node.right)    # right subtree

def permutations(arr, current=[]):
    if len(current) == len(arr):
        print(current)
        return
    for num in arr:
        if num not in current:
            current.append(num)      # choose
            permutations(arr, current)
            current.pop()            # undo (backtrack)

# Not tail recursive — multiplication happens after return
def factorial(n):
    if n == 0: return 1
    return n * factorial(n-1)  # multiply after recursive call
 
# Tail recursive — accumulator carries the result
def factorial_tail(n, acc=1):
    if n == 0: return acc
    return factorial_tail(n-1, n * acc)  # last operation is the call