from operator import add, mul
from math import sqrt, e

# Recursion
def factorial_iter(n):
    """Compute the factorial of a natural number.

    >>> factorial_iter(6)
    720
    """
    if n == 0 or n == 1:
        return 1
    total = 1
    while n >= 1:
        total, n = total * n, n - 1
    return total

def factorial(n):
    """Compute the factorial of a natural number.

    >>> factorial(6)
    720
    """
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

# a, factorial = factorial 3
# a(4)

# Reverse order recursion
def factorial2(n):
    """Compute the factorial of a natural number.

    >>> factorial2(6)
    720
    """
    return factorial_helper(n, 1)

def factorial_helper(n, k):
    if k >= n:
        return k
    else:
        return k * factorial_helper(n, k + 1)

# Tree recursion
def fib_iter(n):
    """Compute the nth Fibonacci number.

    >>> fib_iter(6)
    8
    """
    if n == 0:
        return 0
    fib_n, fib_n_minus_1 = 1, 0
    k = 1
    while k < n:
        fib_n, fib_n_minus_1 = fib_n_minus_1 + fib_n, fib_n
        k += 1
    return fib_n
    
def fib(n):
    """Compute the nth Fibonacci number.

    >>> fib(6)
    8
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)