Advanced Recursion Techniques

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\)

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?
\(f(0)=0\)

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.

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?
\(f(0)=(0,0)\)

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

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?
\(f(0)=(0,0,0)\)

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?