Learn

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

Instructions

1.

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 1 for such inputs.
2.

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

Take this course for free

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?