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 comes just before it.

Watch the video for an introduction to recursion in Desmos, and read on to learn more.

To provide a recursive definition for a sequence in Desmos, you’ll need to know the sequence’s first term or terms (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 the sequence. What would \(f(120)\) equal?

You must define a base case before the calculator can evaluate a recursive function. Recursive functions that rely on more than one term in the sequence require multiple base cases.

If you forget to add base cases for your recursive function, the calculator will prompt you. For example, for a recursive function \(f(n)\), you can add \(f(1)\).

Most examples you'll see start with \(0\) or \(1\) as the first base case. In the previous example, 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).\)

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.

A practical application of recursive sequences is 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.

You can write any sequence in piecewise notation that you can in function notation.

Let’s continue with the sequence \(3,5,7,9,11\),....

The first term is \(3\), and you can find each new term 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 shows that when \(n=1\), then \(f(n)=3\). Otherwise, \(f(n)\) is defined as \(f(n-1)+2\). Open the Recursion Syntax example graph to compare function and piecewise notations.

In the Geometry Tool, you can apply a recursive function to geometric objects. Recursion can help explore unique geometric relationships, such as repeatedly applying a transformation to an object.

As an example, define a translation function \(T(x)=\) translate\((x,\) vector). This function translates any object \(x\) in the direction and magnitude of the vector.

You can then use that function in a recursive function, \(f(n)=T(f(n-1))\), which will create a sequence where each new term is the translation of the previous term. After defining a base case \(f(0)=\), insert the token of your initial object by pressing Shift and then clicking on the object.

Once you have defined the sequence, \(f(1)\) shows the translation applied once, \(f(2)\) shows the translation applied twice, and so on.

Open the Geometry example graph to see how changing the vector affects the sequence or to try your own transformation.

As soon as you type a recursive rule such as \(f(n)=f(n-1) + 2\), you will be prompted to add a base case.

Typically, sequences start with \(n=0\) or \(n=1\). Continuing with the earlier example, let’s set \(f(1)=3\).

Since the rule looks at the \(n-1\) term and the base case is when \(n = 1\), the 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 you make a recursive call outside of the domain, such as \(f(2.5)\), the calculator will show the function as undefined. This is because the recursive rule will look back one to \(f(1.5)\) and then \(f(0.5)\). Thus, it can’t reach the base case.

When creating a recursive function with decimal arguments, there may be unexpected times the calculator returns a function as undefined due to floating point arithmetic.

For example, consider the recursive function \(f(x)={x=0:5,f(x-0.1)}\), which defines a base case as \(f(0)=5\) and each term \(f(x)\) is equal to the term \(f(x-0.1)\). From that definition, we might expect \(f(0)=f(0.1)=f(0.2)=f(0.3)=...=5\). However, you may observe that some values of \(x\) return as undefined. This is because Desmos's system defines decimals internally using a floating point approximation. As \(0.1\) is repeatedly subtracted from the term number, the sequence of decimals that internally defines it doesn’t always reach precisely \(0\). Because of this, we recommend using integers for the arguments of recursive function, as arithmetic on integers is more often exact.

As an alternative workaround, try using inequalities for the base case. In the previous example, if you instead set the base case to \(x\le0:5\), even if the recursive call doesn’t exactly hit the base case, the recursive call will still be defined.

Read more about the double-precision floating point arithmetic Desmos uses in our More Intuitive Calculator Arithmetic blog post.

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.

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.