# Recursive factorial

def factorial(n):
    """Return the factorial of n.

    >>> factorial(0)
    1
    >>> factorial(1)
    1
    >>> factorial(5)
    120
    """
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)


# Sum digits

def sum_digits(n):
    """Return the sum of the digits of positive integer n.

    >>> sum_digits(9)
    9
    >>> sum_digits(18117)
    18
    >>> sum_digits(9437184)
    36
    >>> sum_digits(11408855402054064613470328848384)
    126
    """
    if n < 10:
        return n
    else:
        return sum_digits(n//10) + n%10


# Count up to a number with print expressions
# With recursion by enumeration first since it's a bit easier to demonstrate

def count_up(n):
    """Recursively print up to n.

    >>> count_up(5)
    1
    2
    3
    4
    5
    """
    if n == 1:
        print(1)
    elif n == 2:
        print(1)
        print(2)
    elif n == 3:
        print(1)
        print(2)
        print(3)
    elif n == 4:
        count_up(3)
        print(4)
    else:
        count_up(n - 1)
        print(n)


# Now, a cleaned-up version

def count_up(n):
    """Recursively print up to n.

    >>> count_up(5)
    1
    2
    3
    4
    5
    """
    if n >= 1:
        count_up(n - 1)
        print(n)


# Iterative factorial
# Key idea in converting recursion to iteration: try to make the state
# maintained in each iteration the same as the state maintained by each
# recursive call

def fact_iter(n):
    total, k = 1, 1
    while k <= n:
        total, k = total * k, k + 1
    return total


# Converting back to recursion
# More formulaic: whatever state is maintained in each iteration, pass
# that in as arguments to the recursive function

def fact2(n, total):
    if n == 0:
        return total
    else:
        return fact2(n-1, total*n)

# Can be ugly or complicated, but often not too hard to clean up

fact = lambda n: fact2(n, 1)