f[x] applies f to x. f[f[x]] applies f to f[x], or effectively nests the application of f. It’s common to want to repeat or nest a function.

NestList[f,x,4]

NestList[Framed,x,5]

If you want to see a list of the results of successive nestings, use NestList. If you only want to see the final result, use Nest.

Nest[Framed,x,5]

Nestedly apply EdgeDetect to an image, first finding edges, then edges of edges and so on.

NestList[EdgeDetect,,6]

NestList[ColorNegate[EdgeDetect[#]]&,,6]

Start with red, and nestedly blend with yellow, getting more and more yellow.

NestList[Blend[{#,Yellow}]&,Red,20]

If you successively apply a function that adds 1, you just get successive integers.

NestList[#+1&, 1, 15]

Nestedly multiply by 2, getting powers of 2.

NestList[2*#&,1,15]

NestList[#^2&,2,6]

You can make nested square roots too.

NestList[Sqrt[1+#]&,1,5]

NestList[Sqrt[1+#]&,1,10]//N

RandomChoice randomly chooses from a list. You can use it to create a pure function that, say, randomly either adds +1 or −1.

NestList[#+RandomChoice[{+1,-1}]&,0,20]

ListLinePlot[NestList[#+RandomChoice[{+1,-1}]&,0,500]]

So far, we’ve used NestList iteratively—effectively to perform a chain of applications of a particular function. But you can also use it for recursion, in which the very pattern of applications of the function is itself nested.

NestList[f[#]&,x,3]

NestList[f[#,#]&,x,3]

NestList[Framed[f[#,#]]&,x,3]

Putting everything in columns shows the nested pattern of function applications.

NestList[Framed[Column[{#,#}]]&,x,3]

NestList[Framed[Grid[{{#,#},{#,#}}]]&,x,3]

NestList[Framed[Grid[{{0,#},{#,#}}]]&,x,3]

NestList[Flatten[{#,Rotate[#,90°],Rotate[#,270°]}]&,"R",4]

Not all results from recursion are so complicated. Here’s an example that successively adds two shifted copies of a list together, as in {0,1,2,1}+{1,2,1,0}.

NestList[Join[{0},#]+Join[#,{0}]&,{1},5]

NestList[Join[{0},#]+Join[#,{0}]&,{1},8]//Grid

Here’s another example of recursion with NestList.

NestList[{f[#],g[#]}&,x,3]

Even if things are arranged in columns, it’s still quite difficult to understand the structure that’s been created.

NestList[Column[{f[#],g[#]}]&,x,3]

NestGraph is basically like NestList, except that it makes a graph rather than a list. It repeatedly applies a function to determine what nodes a particular node should connect to. In this case, it produces a tree of nodes, making it clearer what’s going on.

NestGraph[{f[#],g[#]}&,x,3,VertexLabels->All]

NestGraph[{2#,2#+1}&,0,4,VertexLabels->All]

You can use NestGraph to effectively “crawl” outward creating a network. As an example, we can repeatedly apply a function that for any country gives a list of countries that border it. The result is a network that connects bordering countries, here starting with Switzerland.

NestGraph[#["BorderingCountries"]&,LinguisticAssistant,2,VertexLabels->All]

As another example, start from the word “hello” and successively connect every word to 3 words in the list of common words that Nearest considers nearest to it.

NestGraph[Nearest[WordList[ ],#,3]&,"hello",4,VertexLabels->All]

Make a list of the results of nesting Blur up to 10 times, starting with a rasterized size-30 “X”. »

Start with x, then make a list by nestedly applying Framed up to 10 times, using a random background color each time. »

Start with a size-50 “A”, then make a list of nestedly applying a frame and a random rotation 5 times. »

Make a line plot of 100 iterations of the logistic map iteration 4 #(1-#)&, starting from 0.2. »

Find the numerical value of the result from 30 iterations of 1+1/#& starting from 1. »

Create a list of the first 10 powers of 3 (starting at 0) by nested multiplication. »

Make a list of the result of nesting the (Newton’s method) function (#+2/#)/2& up to 5 times starting from 1.0, and then subtract (Sqrt[2])from all the results. »

Make graphics of a 1000-step 2D random walk which starts at {0,0}, and in which at each step a pair of random numbers between −1 and +1 are added to the coordinates. »

Make an array plot of 50 steps of Pascal’s triangle modulo 2 by starting from {1} and nestedly joining {0} at the beginning and at the end, and adding these results together modulo 2. »

Generate a graph by starting from 0, then nestedly 10 times connecting each node with value n to ones with values n+1 and 2n. »

Generate a graph obtained by nestedly finding bordering countries starting from the United States, and going 4 iterations. »

Make a line plot of 100 iterations of linear congruential function Mod[59#,101]&, starting from 1. »

Create a list of 5 power towers of 2, i.e. 2^2^2...^2 n times, with n from 0 to 4. »

Create a list of 20 power towers of 1.2, i.e. 1.2^1.2^...^1.2  n times, with n from 0 to 19. »

Generate a list of the numerical values obtained by up to 10 nestings of the function Sqrt[1+#]&. »

Make graphics of a 1000-step 3D random walk which starts at {0,0,0}, and in which at each step a triple of random numbers between −1 and +1 are added to the coordinates. »

What’s the difference between iteration and recursion?

If one does one thing repeatedly, it’s iteration. When one takes the result of an operation and applies the same operation to it wherever it is, that’s recursion. It’s slightly confusing, because simple cases of recursion are just iteration. NestList always does recursion, but if only one slot appears in the function, the recursion can be “unrolled” into iteration.

What is the relation between nesting, recursion and fractals?

They are very closely related. The definitions aren’t precise, but fractals are basically geometrical forms that exhibit some type of nested or recursive structure.

What is Pascal’s triangle?

It’s a very common structure discussed in elementary mathematics. Its definition is very close to the Wolfram Language code here: at each row each number is computed as the sum of the numbers directly above it and above it to its right. Each row gives the coefficients in the expansion of (1+x)^n.

Is NestGraph like a web crawler?

Conceptually yes. One can think of it as doing the analog of starting from a webpage and then visiting links from that page, and continuing recursively with that process. We’ll see an example of this in Section 44.

Why do some but not all countries have arrows both ways in the bordering countries graph?

If NestGraph was run for enough steps, all countries would have arrows both ways, since if A borders B, then B borders A. But here we’re stopping after just 2 steps, so many of the reverse connections haven’t been reached.

Why use NestList for something like NestList[2*#&,1,15]?

You don’t need to. You can just use Power, as in Table[2^n,{n,0,15}]. But it’s nice to see the sequence Plus, Times, Power arise from successive nesting (e.g. NestList[2+#&,0,15] is Table[2*n,{n,0,15}]).

Is there a way to keep applying a function until nothing is changing?

Yes. Use FixedPoint or FixedPointList (see Section 41).

Tech Note