Lesson goal: Evaluating a recurrence relation using arrays

Previous: Arrays and averaging numbers | Home | Next: Arrays and histograms

In a past lesson, you learned about arrays, and how they allow you to store a sequence of data under the same variable name.

In this lesson, let's use arrays to evaluate a "recurrence relation." Here is the recurrence relation (from Salkind, 1966): $F(n+1)=\frac{2F(n)+1}{2}$, given that $F(1)=2$.

Hopefully, you can see why this is a "recurrence relation." Suppose we wanted to find $F(2)$. Putting $n=2$ into the above relation, we'll get $F(2)=\frac{2F(1)+1}{2}$. As you can see, in order to find $F(2)$, we need to know what $F(1)$ is. Luckily here, $F(1)$ is given to be $2$ (most recurrence relations are given with some starting value like this). Notice that the function is defined in terms of itself--this is called a "recursive function" and is why the relation is called a "recurrence relation."

Given all of this, your job is to evaluate $F(101)$.

Now you try. Fix the for loop and program in the recurrence relation to find F[101]!

Type your code here:

See your results here:

In this code, we've started you out by setting up the array F, and that we know F[1]=2. Fix the for-loop to run over the proper values of n. Next program in the recurrence relation into the F[n]= line.

When done, try this recurrence relation: $F(n)=F(n-1)+F(n-2)$, given that $F(0)=0$ and $F(1)=1$. Evaluate all $F$'s from $n=2$ to $10$. The numbers you generate are called "Fibonacci Numbers." Dismiss.

Show a friend, family member, or teacher what you've done!

Here is a share link to your code:

Does your code work? Want to run it on your iPhone?

Here's your code:

  1. Use [Control]-[C] (Windows) or [⌘]-[C] (MacOS) to copy your code.

  2. Paste it using [Control]-[V] (Windows) or [⌘]-[V] (MacOS) into this page

  3. Then click the "Use on iPhone" button that you'll see.