# Compute numbers in the Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

# Compute the nth Fibonacci number using recursion
# Parameters:
#   n: The Fibonacci number to computer
# Returns: The nth Fibonacci number
def fib(n):
  # Base cases
  if n == 0:
    return 0
  if n == 1:
    return 1

  # Recursive case
  return fib(n-1) + fib(n-2)

# Compute the nth Fibonacci number using iteration
#   n: The Fibonacci number to computer
# Returns: The nth Fibonacci number
def ifib(n):
  # Deal with the simple cases that don't require any looping
  if n == 0:
    return 0
  if n == 1:
    return 1

  # Keep track of the two previous Fibonacci numbers
  prev_2 = 0
  prev_1 = 1
  # Compute the nth Fibonacci number
  for i in range(2, n+1):
    f = prev_2 + prev_1
    prev_2 = prev_1
    prev_1 = f

  return f


# Compute a Fibonacci value requested by the user using both the iterative
# and recursive functions
n = int(input("Enter an integer: "))
print("ifib(",n,") is", ifib(n), "-- computed using a loop")
print("fib(",n,") is", fib(n), "-- computed using recursion")