# Recursively appending elements to a list

In wanting to demonstrate the power of Mathematica, I wanted to show my 11-year-old son how we could validate that his sequences homework was correct. We could generate the next value in sequence in a simple expression, but when it came to repeatedly doing this (for the next 10 values), I got stuck.

We have seed list of values {0,2,2,4} which we called seedlist. The sequence is simply taking the last two numbers and adding them together to create the next number.

What I wanted to show was how we could generate an extended list for the first 10 (say) values e.g.

{0, 2, 2, 4, 6, 10, 16, 26, 42, 68}


In an attempt to append the next value into the list we did the following

Append[seedlist, (Extract[seedlist, 3] + Extract[seedlist, 4])]


Now I wanted to be able to recursively append to the list. So I tried several approaches as follows:

1. Tried to use a function and the called NestList:

rec[dat_, n_] :=
Append[seedlist, (Extract[seedlist, n] + Extract[seedlist, n - 1])]

NestList[rec[#, i] &, seedlist, {i, 1, 10}]


This gave me an error "Non-negative machine-sized integer expected at position 3 in NestList[rec[#1,i]&,{0,2,2,4},{i,1,10}]"

1. After a bit more digging in the documentation, I then tried a simpler version

NestList[Append[
Rest[#], (Extract[#, 4] + Extract[#, 4 - 1])] &, seedlist, 7]


This worked to a degree but I got presented with the following list

{{0, 2, 2, 4}, {2, 2, 4, 6}, {2, 4, 6, 10}, {4, 6, 10, 16}, {6, 10, 16, 26},
{10, 16, 26, 42}, {16, 26, 42, 68}, {26, 42, 68, 110}}


This has all the answers, just not necessarily in the right places! This is, without necessarily knowing it, what I asked for in the above of course but not what I want to achieve.

I'd be really grateful for someone to point me in the right direction and get the correct list out. I have a feeling I'm fairly close with the last attempt, but I'd appreciate a nudge to solve this correctly.

• NestList[Append[#, #[[-2]] + #[[-1]]] &, seedlist, 7] – Karsten 7. Oct 23 '15 at 11:42
• and +1 for preaching MMA to the younger generation – LLlAMnYP Oct 23 '15 at 11:46
• LinearRecurrence[{1, 1}, {0, 2}, 10] is the built-in, by the way, or RecurrenceTable[{a[n + 1] == a[n] + a[n - 1], a[1] == 2, a[0] == 0}, a, {n, 0, 10}]. (Much less pedagogical value to those.) – Patrick Stevens Oct 23 '15 at 11:56
• You might be interested in linked lists, too, to avoid the fact that Mathematica's Append function doesn't work in-place and so is quite slow: Nest[{#[[2, 1]] + #[[1]], #} &, {2, {0}}, 10] // Flatten // Reverse – Patrick Stevens Oct 23 '15 at 12:00
• I did a small performance benchmark for Tribonacci numbers. SequenceFoldList did perform pretty well. – Karsten 7. Oct 23 '15 at 12:42

What you have is what's known in some circles as a linear recurrence. That is, you have a sequence where the general term can be expressed as an appropriate combination of previous terms.

The simplest way of going about it, as has been previously noted, is to use either of Nest[]/NestList[], like so:

NestList[Append[#, Total[Take[#, -2]]] &, {0, 2, 2, 4}, 6]
{{0, 2, 2, 4}, {0, 2, 2, 4, 6}, {0, 2, 2, 4, 6, 10}, {0, 2, 2, 4, 6, 10, 16},
{0, 2, 2, 4, 6, 10, 16, 26}, {0, 2, 2, 4, 6, 10, 16, 26, 42},
{0, 2, 2, 4, 6, 10, 16, 26, 42, 68}}


where Take[list, -2], takes the last two (hence the negative sign) elements, and Total[list] sums the two elements up.

However, it should be said that there is a function called, appropriately enough, LinearRecurrence[], that does this recursion in an efficient manner. Here is how to use it:

LinearRecurrence[{1, 1}, {0, 2}, 10]
{0, 2, 2, 4, 6, 10, 16, 26, 42, 68}


To explain the notation a bit, LinearRecurrence[{1, 1}, {a, b}, k] generates k terms, starting with the first two terms a and b, and then successively generates a + b, a + 2 b, 2 a + 3 b, .... You can see this by feeding symbolic arguments:

LinearRecurrence[{1, 1}, {a, b}, 10]
{a, b, a + b, a + 2 b, 2 a + 3 b, 3 a + 5 b, 5 a + 8 b, 8 a + 13 b,
13 a + 21 b, 21 a + 34 b}


In fact, your sequence can be expressed in terms of the famous Fibonacci numbers, which satisfy the same recursion, but with different starting points. I'll skip the (deep!) math, but here's a demonstration:

Table[2 (Fibonacci[n - 3] + Fibonacci[n - 2]), {n, 9}]
{0, 2, 2, 4, 6, 10, 16, 26, 42, 68}

• J.M. Excellent information again. I'll point out the Fibonacci bit to my son. I hadn't previously seen LinearRecurrence. I'll go play... Thanks Anthony – AnthonyMiller Oct 23 '15 at 12:04
• The fact that this is Fibonacci-derived means that there is a closed form for the solution, too. Mathematica will find it: FindSequenceFunction[{0, 2, 2, 4, 6, 10, 16, 26, 42, 68}, x] // FunctionExpand // FullSimplify[#, x ∈ Integers] & – Patrick Stevens Oct 23 '15 at 12:07
• @Patrick, yes, but I'm not too sure the kid will appreciate Binet at this stage. :) – J. M.'s torpor Oct 23 '15 at 12:08
• @J.M. What do you mean?! All you have to do is diagonalise the appropriate matrix ;) – Patrick Stevens Oct 23 '15 at 12:09
• I'm confused, why not go all the way with 2 Table[Fibonacci[n - 1], {n, 9}]? If you divide the starting numbers by 2, this is immediately clear, right? – Jacob Akkerboom Oct 24 '15 at 16:01
NestList[Append[#, #[[-2]] + #[[-1]]] &, {0, 2, 2, 4}, 5]


[[-2]] means the second last element; # instead of Rest[#] is used to prevent discarding of the first element. As we can count elements from the end, we don't have the problem of needing to know the length of the seed list. We might as well have done

NestList[Append[#, #[[-2]] + #[[-1]]] &, {0, 2}, 7]

• Excellent. Thank you for giving me two answers :-) – AnthonyMiller Oct 23 '15 at 12:01

It can be done elegantly with tail recursion.

series[a_, b_, n_] := Flatten[helper[a, b, n, {}]]
helper[_, _, 0, s_] := s
helper[a_, b_, n_, s_] := helper[b, a + b, n - 1, {s, a}]

series[0, 2, 10]


{0, 2, 2, 4, 6, 10, 16, 26, 42, 68}

When the 1st two arguments are set to 1, series gives the Fibonacci series.

series[1, 1, 10] == Table[Fibonacci[i], {i, 10}]


True

• Is there is reason why you are using the undefined term. I tried using List instead and it's even faster. – Karsten 7. Oct 23 '15 at 19:23
• @Karsten7.Habit. Most of my tail-recursive code deals with accumulating lists of some complexity. I have become habituated to using a tag when accumulating them into a linked structure to make the final flattening easier. As you point out, there is no need for that here. I will edit my answer accordingly. – m_goldberg Oct 23 '15 at 22:03

Another approach is to use recursion. If you don't have a large number simple recursion will do, but if the sequence you are creating is big you can speed it up (at the expense of memory) by using Set when you define the function (a method called memoization).

func[n_] := func[n] = func[n - 1] + func[n - 2]
func[1] = 0;
func[2] = 2;


This function won't give you the list but rather provides you with the value.

func[10]
(* 68 *)


Now however, if you examine func you will see

?func


All of the intermediate values have been assigned.

To create the desired list use Map.

Map[func, Range[10]]
(* {0, 2, 2, 4, 6, 10, 16, 26, 42, 68} *)


Your sequence satisfies the following recursive formula

$a_{n+1} = a_n + a_{n-1}(n\geq 1) \quad a_0=0, a_1=2$

Trying this

First /@ NestList[{#2, #1 + #2} & @@ # &, {0, 2}, 9]

{0, 2, 2, 4, 6, 10, 16, 26, 42, 68}


For the general formula $a_{n+1}=$ func $(a_{n-1},a_n)$, you can use the a general solution

# & @@@NestList[{#2, func[#1,#2]} & @@ # &, {a1, a2}, n]

where $n$ is the $n$-th number

For recursion formula $a_{n}=\alpha a_{n-1}+\beta a_{n-2}\quad (n \geq 2)$

we can use the following strtegy.ie. built-in MatrixPower[].

$$\begin{pmatrix} a_{n-1}\\ a_{n} \end{pmatrix} = \begin{pmatrix} a_{n-1}\\ \alpha a_{n-1}+\beta a_{n-2} \end{pmatrix} = \begin{pmatrix} 0 & 1\\ \beta & \alpha \end{pmatrix} \begin{pmatrix} a_{n-2}\\ a_{n-1} \end{pmatrix}$$ $$=\cdots = \begin{pmatrix} 0 & 1\\ \beta & \alpha \end{pmatrix}^{n-2} \begin{pmatrix} a_{1}\\ a_{2} \end{pmatrix} =A^{n-2}\begin{pmatrix} a_{1}\\ a_{2} \end{pmatrix}$$

where, $A= \begin{pmatrix} 0 & 1\\ \beta & \alpha \end{pmatrix}$

I like everyone's answers, but it seems to me that your first approach is most appropriate for a 11-year-old kid new to MMA. Keep it simple and leave the pure functions and exotic syntax for another day. :)

Perhaps something like this:

next[list_] := Append[list, list[[-1]] + list[[-2]]]


So that

next[{0, 2, 2, 4}]


returns

{0,2,2,4,6}


Then

Nest[next, {0, 2, 2, 4}, 10]


returns

{0, 2, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466}


After all, you're trying to show how simple and easy it is to check your homework with MMA :)