# 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

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?

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.

## 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.

## 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.

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.

## Recursion in Geometry

In Desmos Geometry, 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. This can now be used 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. To define a base case $$f(0)$$, begin by typing f(0)=, and insert the token of your initial object by using shift + click on the object. Now that the sequence of translations has been defined, 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.

## 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.

When creating a recursive function with decimal arguments, there may be unexpected times Desmos returns “undefined,” due to how recursion is calculated internally using 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 ‘undefined.’ This is because our 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 above example, if we instead set the base case to $$x \le 0: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.

### 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.”

## Learn More

Please write in with any questions or feedback to support@desmos.com.