Skip to main content

Recursion

  • function that calls itself
  • Applications: Dynamic Programming, Backtracking, Divide and Conquer
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

Tail Recursion​

  • A function is tail recursive if the function does not do anything after the last recursive call
  • Modern compilers replace tail recursion with goto -> Tail call elimination
def fun(n):
    if n <= 0:
        return
    print(n)
    fun(n)
info

Python does not do tail call elimination