As you learned in your Data Structures and Algorithms course, a recursive function is a function that computes a value by making a call to itself. This implies that a recursive function uses previous values to compute new ones. To prevent an infinite loop, a recursive function terminates when a base case is reached.
The general template for a recursive function is:
- First, evaluate the base case(s) of the function. These serve as the termination point for the recursion.
- If the base cases are not reached, perform necessary operations and then call the function again.
- Return the computed value.
The most common example of this is the Fibonacci sequence. It is written in Python as follows:
def fib(n): if n < 2: return n k = fib(n - 1) + fib(n - 2) return k # Alternatively, you can simply return fib(n - 1) + fib(n - 2) without assigning it to a variable
Complete the Python function
factorial(n) that recursively computes n!. Remember the following identities:
- 0! = 1
- Factorials are not defined for numbers less than zero; your function should return
1for such inputs.
A modified Fibonacci sequence is a sequence of numbers in which each number is the sum of the preceding three numbers (as opposed to two). Complete the Python function
mod_fib(n) that computes the nth number in this sequence.
Use these initial conditions:
- F(0) = 0
- F(1) = 1
- F(2) = 2