Python Practice 11/22

Recursion kata: factorial and Fibonacci

A recursive function calls itself with a smaller version of its own input, until it reaches a base case small enough to answer directly without calling itself again. Every recursive function needs both parts: a base case that stops the calls, and a step that shrinks the input and trusts the smaller call to return the right answer.

5! (factorial) is 5 * 4!, and 4! is 4 * 3!, all the way down to 0! = 1 - the base case that ends the chain. Fibonacci works the same way: each number is the sum of the two before it (fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)), down to two base cases, fibonacci(0) = 0 and fibonacci(1) = 1.

Your task: write factorial(n), returning n! using recursion (0! is 1). Then write fibonacci(n), returning the nth Fibonacci number (0-indexed: fibonacci(0) = 0, fibonacci(1) = 1) using recursion - each function should call itself, not use a loop.

You'll practice:

Writing a base case and a recursive case for factorial
Writing a two-base-case recursive function for Fibonacci

# Write factorial(n): n! using recursion. 0! is 1.
def factorial(n):
    pass

# Write fibonacci(n): the nth Fibonacci number using recursion.
# fibonacci(0) is 0, fibonacci(1) is 1.
def fibonacci(n):
    pass