Recursion

A recursive sequence is defined when the value of a term depends on one or more other terms in the sequence. Typically, the value of the term relies on the term (or terms) that came just before it. Get started with the video on the right, then learn more about sequences that rely on previous terms below.

 

Getting Started - Function Notation | Base Cases | Fibonacci Sequence | Compound Interest | Getting Started - Piecewise Notation | Undefined Recursive Terms | Learn More

 

Getting Started - Function Notation

To provide a recursive definition for a sequence in Desmos, you’ll need to know the sequence’s first term or terms (we call them base cases), and the rule to find each term after that. Let’s try an example.

Consider the sequence whose first few terms are \(3,5,7,9,\) and \(11\). We can think about this as a recursive sequence, where the first term (or base case) is \(3\), and the recursive rule is to add \(2\) to the previous term.

To enter this in the calculator, follow these steps:

  1. Define a function that describes the rule:
    \(f(n) = f(n-1) + 2\)
  2. Define your base case:
    \(f(1) = 3\)

In the recursive rule, \(f(n-1)\) indicates the previous term. Once your recursive sequence is defined, you can use the function to find other terms. Try finding the 25th term of our sequence in this example graph. What would \(f(120)\) equal?

GIF showing a recursive function and using the Create Table button which graphs the first 5 terms in the sequence.

Hint: If you select the ‘create table’ button in the same line as your recursive definition, we’ll add a table of the first 5 terms in your sequence for you.

 

Base Cases

  • Most examples you'll see start with \(0\) or \(1\) as the first base case. In the example above, we could have defined \(f(0) = 3\) or \(f(1) = 3\). If you start with \(0\), then \(f(1)\) would be the second term in your sequence. If you start with \(1\), the second term is \(f(2)\).
  • If you forget to add base cases for your recursive function, we’ll prompt you. For example, for a recursive function \(f(n)\) you can add \(f(1)\).
  • Base cases need to be defined before we can evaluate the recursive function.
  • Recursive sequences that rely on more than one term in the sequence require multiple base cases.
Screenshot of the expression list showing the add base case button.

 

Fibonacci Sequence

You may be familiar with the Fibonacci sequence or its connection to nature with the Fibonacci spiral. This recursive sequence is defined by adding together the two previous terms. 

Here are the first few terms: \(1,1,2,3,5,8,\)…
What’s the rule?
Add the previous two terms: \(g(n)=g(n-1)+g(n-2)\)
What are the base cases?
\(g(1)=1\), \(g(2)=1\)

From the Fibonacci sequence, you can create the Fibonacci spiral by constructing squares with side lengths following the Fibonacci sequence and drawing arcs through the opposite corners of these squares. Open this Fibonacci spiral example graph to explore the connection between the sequence and the spiral.

Screenshot of the Fibonacci spiral and the expression list showing the Fibonacci sequence defined recursively.

 

Compound Interest

A practical application of recursive sequences can be found when working with compound interest. To calculate how much money you can earn, you need an initial investment amount, and a set rate. With a recursive sequence, you can easily change the initial investment, rate, or see what happens if you add yearly contributions. We’ll start with an initial investment of \($100\) that earns \(10\%\) per year.

Here are the first few years of interest: \($100, $110, $121, $133.10\),...
What’s the rule?
Take \(110\%\) of the year prior: \(f(n) = 110\%\) of \(f(n-1)\)
What’s the base case?
\(f(0) = $100\)

Without recursion, the compound interest formula \(P=I(1+r)^t\) can tell you the amount of money you’ll have after \(t\) years where \(P\) is the principal amount, \(I\) is the initial investment, and \(r\) is the rate. The initial investment, rate, and amount of time is adjustable, but this equation can’t model what would happen if you want to contribute more to your investment.

Side by side screenshot comparing the Recursive Formula and Interest Formula to calculate compound interest.

To model adding an extra \($100\) a year in the recursive formula, simply add \(100\) to the original rule \((f(n) = 110\%\) of \(f(n-1) + 100)\). Open this compound interest example graph to see the recursive formula, interest formula, and additional contribution examples.

 

Getting Started - Piecewise Notation

Any sequence you write in function notation can also be written in piecewise notation. Let’s continue with the sequence \(3,5,7,9,11\),....

We know the first term is \(3\), and each new term can be found by adding \(2\) to the previous term. In piecewise notation, we write this as \(f(n) = \{n=1:3, f(n-1) + 2\}\). This syntax says “when \(n = 1\), then \(f(n) = 3\). Otherwise, \(f(n)\) is defined as \(f(n-1) + 2\).” Open the example graph to compare function and piecewise notations.

Side by side screenshot comparing Function Syntax and Piecewise Syntax to write a rule that adds 2 to the previous term with a base case of 3.

 

Undefined Recursive Terms

When working with recursive functions in Desmos, you may unexpectedly find that a certain term is undefined. A couple reasons this might be happening is the calculator cannot reach a base case or the recursion depth limit is reached.

Can't Reach a Base Case

As soon as we type a recursive rule such as \(f(n) = f(n-1) + 2\), we are prompted to add a base case. Typically, we start with \(n = 0\) or \(n = 1\). Continuing with our example above, let’s set \(f(1) = 3\). Since our rule looks at the n-1 term and we defined our base case when \(n = 1\), our function is defined on the domain of positive integers. In other words, \(f(2)\), \(f(3)\), \(f(4)\), and so on will be defined.

If we make a recursive call outside of the domain, such as \(f(2.5)\), Desmos will return “undefined.” This is because the recursive rule will look back one to \(f(1.5)\) and then \(f(.5)\). Thus, it can’t reach our base case.

Screenshot of f(n)=f(n-1)+2 with a base case f(1)=3 showing that f(2.5) returns undefined.

 

Reached Recursion Depth Limit

One other way to get an undefined term from a recursive call is reaching the recursion depth limit. After 10,000 attempts, if Desmos can’t find a base case, it returns undefined. Let’s look at an example.

Consider the recursive function \(f(x) = \{x=0: 1, f(x-1)\}\). Starting with \(f(0) = 1\), this defines every term to be equal to the previous term. That is, \(f(2)\) will equal \(f(1)\), which will equal \(f(0)\), which is our defined base case. However, while this function should always return 1 for positive integer values, it will return \(f(10001) =\) undefined. Evaluating \(f(10001)\) would require more than 10,000 steps to reach a base case (in this case, looking one term backwards each time), so, although it exists, the calculator returns “undefined.”

Screenshot of the recursive rule f(x)=f(x-1) and the base case is f(0) = 1 represented in piecewise notation. It shows f(1) = 1 and f(2) =2 but f(100001) = undefined.

 

Learn More