Advanced Recursion Techniques

Some advanced recursion techniques include defining recursive sequences in terms of other recursive sequences with mutual recursion and using the random() function in a recursive rule to create random walks. Get started with our Recursion article and dive deeper with the examples below.


Mutual Recursion

A mutually recursive group of functions is defined when two or more functions are defined in terms of each other. To get started, you’ll need at least two sequences. Let’s consider the following example:

Sequence one begins with \(0,1,0,-1,0,\) and \(1\).
Sequence two begins with \(1,0,-1,0,1,\) and \(0\).

Both of these sequences repeat every four terms and represent the x-intercept, min, and max of the cosine and sine function, respectively. To write mutually recursive rules for these sequences, let’s use \(f(x)\) for sequence one and \(g(x)\) for sequence two.

What’s the rule for sequence one?
Each term of sequence one is equal to the previous term of sequence two.
\(f(x) = g(x-1)\)

What’s the base case?
\(f(0) = 0\)

Screenshot showing f(x)=g(x-1) with f(0)=0 and g(x)=-f(x-1) with g(0)=1. There's a table created which plots the first 5 points of each sequence.

What’s the rule for sequence two?
Each term of sequence two is equal to negative one times the previous term of sequence one.
\(g(x) = -f(x-1)\)

What’s the base case?

To graph the sequence, press the ‘Create Table’ button next to \(f(x)\) and add another column for \(g(x)\). Explore the recursive relationship between the cosine and sine functions by clicking on the image.


Random Walks

In a random walk, each step is a random distance or direction from the step before. In Desmos, we can represent this with a recursively defined function using random(). Let's look at a few examples.


One-Dimensional Random Walk

GIF showing the graph of the first 101 points of the sequence f(n)=f(n-1) + random([-1,1]) with base case f(0)=0. Then pressing the 'Randomize' button to change the values of the function and the graph.

A random walk in one dimension creates a sequence of numbers. In the following example, each new term is taking a single “step” forward or backward.

The sequence will start at \(0\) when \(n=0\) and at each subsequent step, randomly choose either \(-1\) or \(1\) to add to the previous term. That is, the second term will either be \(-1\) or \(1\), the third term will add either \(-1\) or \(1\) to the second term, and so on.

What’s the rule?
\(f(n)=f(n-1) +\) random\(([-1,1])\)

What’s the base case?

In this Random Walk Example, we’ve plotted a table to visualize the first 101 terms in the sequence. In the graph, the x-axis represents the number of steps and the y-axis is the sum of all the random samples up to that step. When you explore the example, you can use the ‘Randomize’ button at the top of the expression list to update each random call.


Two-Dimensional Random Walk

After exploring the one-dimensional random walk, take a look at what might happen if you add a point in any random direction. We’ll explore this example in the Desmos Geometry Tool.

This example uses the glider, circle, and random functions. The glider function takes two inputs: a geometric object and a number - usually between \(0\) and \(1\). For example, glider(segment, \(0.5\)) places a draggable point restricted to the segment at the midpoint (halfway between the endpoints). The circle function requires a center point and a radius. So, circle\(((0,0),1)\) creates a circle centered at \((0,0)\) with radius \(1\). Random() chooses a random number between \(0\) and \(1\).

The recursive rule below for \(f(n)\) will draw a circle with a radius of \(1\) centered at the previous point and then use the glider function to randomly place a point on that circle.

What’s the rule?
\(f(n)=\) glider(circle\((f(n-1),1)\), random\(()\)

What’s the base case?

GIF showing the graph of the first 101 points of the sequence created by f(n)=glider(circle(f(n-1),1), random()) with base case f(0,0). Then pressing the 'Randomize' button which updates the graph.

Open the 2-Dimensional Random Walk Example to explore in the Geometry Tool.


3-Dimensional Random Walk

GIF showing the graph of the first 1001 points of the sequence f(n)=f(n-1) + random() with base case f(0)=(0,0,0). Then pressing the 'Randomize' button to change the graph.

In 3-Dimensions, you can create a random walk where each point moves one unit in either direction along the x, y, or z-axis. To do so, you’ll need to define a list of points to randomly choose from.

To represent a positive or negative step in either the x, y, or z direction, let \(L=[(1,0,0), (-1,0,0), (0,1,0), (0,-1,0), (0,0,1), (0,0,-1)]\). The expression random\((L)\) will randomly select one of those six points.

Now, you can write the rule and base case for the random walk:

What’s the rule?
\(f(n)=f(n-1)+\) random\((L)\)

What’s the base case?

Starting at \((0,0,0)\), each term in this sequence moves one unit in a random direction. To plot the first 1001 points, type \(f([0…1000])\). Continue to experiment with this 3-Dimensional Random Walk Example. What happens as you continue to randomize the sequence? How does changing \(L\) affect the graph?


Learn More

Please write in with any questions or feedback to