"""Lecture 19 examples: recursion"""

from ucb import trace, main, interact

def pig_latin(w):
    """Return the Pig Latin equivalent of English word w."""
    if starts_with_a_vowel(w):
        return w + 'ay'
    return pig_latin(w[1:] + w[0])

def starts_with_a_vowel(w):
    """Return whether w begins with a vowel."""
    return w[0].lower() in 'aeiou'

def fact_iter(n):
    """Return n! for n > 0."""
    total, k = 1, 1
    while k <= n:
        total, k = total*k, k+1
    return total

def fact(n):
    """Return n! for n > 0."""
    if n == 1:
        return 1
    return n * fact(n-1)

def reverse(s):
    """Return the reverse of string s.
    
    >>> reverse('sub')
    'bus'
    """
    if s == '':
        return s
    return reverse(s[1:]) + s[0]

def reverse_iter(s):
    """Return the reverse of string s.
    
    >>> reverse_iter('sub')
    'bus'
    """
    r, i = '', 0
    while i < len(s):
        r, i = s[i] + r, i + 1
    return r

def reverse2(s):
    """Return the reverse of string s.
    
    >>> reverse2('sub')
    'bus'
    """
    def rev(s, r, i):
        if not i < len(s):
            return r
        return rev(s, s[i] + r, i + 1)
    return rev(s, '', 0)

@main
def run():
    interact()