"""
CS 1109, SU2023
Lab 10 - Recursion
Author: YOUR NAME(S) HERE
"""

def termial(n):
    """
    Computes and returns the termial of n, or the sum of the first n
    natural numbers. Recall that a natural number is an integer greater
    than or equal to 0.

    For example, termial(5) would return 5 + 4 + 3 + 2 + 1 = 15.

    Precondition: n is an integer where n >= 0.
    """


def fibonacci(n):
    """
    Returns the nth Fibonacci number.

    The Fibonacci numbers are defined as follows:

    - fibonacci(0) is 0
    - fibonacci(1) is 1
    - fibonacci(n) is equal to fibonacci(n-1) + fibonacci(n-2), or the nth
      Fibonacci number is the sum of the n-1 Fibonacci number and the
      n-2 Fibonacci number.

    Precondition: n is an integer where n >= 0.

    Hint: You will need **two** base cases!
    """

def gcd(a, b):
    """
    Returns the greatest common divisor (gcd) of a and b using
    Euclid's algorithm. Recall that the gcd of a and b is
    the largest number d such that d divides both a and b.

    Note how gcd(a, 0) is `a` as `a` divides both `a` and 0
    (since every integer divides 0) and `a` is the largest number
    that can divide `a`.
    **THIS IS YOUR BASE CASE**

    Otherwise, if b != 0, then we know that
    gcd(a,b) == gcd(b, a % b) as `a % b` is the remainder
    of dividing `a` by `b`.
    **THIS IS YOUR RECURSIVE CASE**

    Precondition: a and b are both non-negative integers.
    """

# EXTRA HARDER RECURSIVE FUNCTIONS:

"""
We can also perform recursion on lists! Consider the
list [1, 2, 3]. Let's rewrite [1, 2, 3] as

[1, 2, 3] = [1] + [2, 3]

That is, a list is composed of the first element of
the list concatenated with the rest of the list.

We could continue this process and rewrite [2, 3]
as:

[2, 3] = [2] + [3]

and again with [3]:

[3] = [3] + [].

Notice how concatenating [3] with [] is equal
to just the list [3] (similar to adding 0 or
multiplying by 1).
"""

def sum_list(ls):
    """
    Returns the sum of the numbers in ls, computed
    recursively.

    Base Case: If ls is [], then sum_list([]) should
               return 0.

    Recursive Case: If ls is not [], then sum_list(ls)
                    should return the sum of ls[0]
                    and the sum of the *rest* of ls,
                    sometimes called the tail.

    Preconditions: ls is a (possibly empty) list of numbers.
    """