Applying Functions Repeatedly

Many programs you write will involve operations that need to be iterated several times. (RefLink[Nest, paclet:ref/Nest]) and (RefLink[NestList, paclet:ref/NestList]) are powerful constructs for doing this.

Applying functions of one argument repeatedly.

(RefLink[Nest, paclet:ref/Nest])[f,x,n] takes the "name" f of a function, and applies the function n times to x:

Nest[f,x,4]

This makes a list of each successive nesting:

NestList[f,x,4]

Here is a simple function:

recip[x_]:=1/(1+x)

You can iterate the function using (RefLink[Nest, paclet:ref/Nest]):

Nest[recip,x,3]

(RefLink[Nest, paclet:ref/Nest]) and (RefLink[NestList, paclet:ref/NestList]) allow you to apply functions a fixed number of times. Often you may want to apply functions until the result no longer changes. You can do this using (RefLink[FixedPoint, paclet:ref/FixedPoint]) and (RefLink[FixedPointList, paclet:ref/FixedPointList]).

Applying functions until the result no longer changes.

Here is a function that takes one step in Newton’s approximation to (Sqrt[3]):

newton3[x_]:=N[1/2 (x+3/x)]

Here are five successive iterates of the function, starting at x==1:

NestList[newton3,1.0,5]

Using the function (RefLink[FixedPoint, paclet:ref/FixedPoint]), you can automatically continue applying newton3 until the result no longer changes:

FixedPoint[newton3,1.0]

Here is the sequence of results:

FixedPointList[newton3,1.0]

Applying functions repeatedly until a test fails.

Here is a function which divides a number by 2:

divide2[n_]:=n/2

This repeatedly applies divide2 until the result is no longer an even number:

NestWhileList[divide2,123456,EvenQ]

This repeatedly applies newton3, stopping when two successive results are no longer considered unequal, just as in (RefLink[FixedPointList, paclet:ref/FixedPointList]):

NestWhileList[newton3,1.0,Unequal,2]

This goes on until the first time a result that has been seen before reappears:

NestWhileList[Mod[5#,7]&,1,Unequal,All]

Operations such as (RefLink[Nest, paclet:ref/Nest]) take a function f of one argument, and apply it repeatedly. At each step, they use the result of the previous step as the new argument of f.

It is important to generalize this notion to functions of two arguments. You can again apply the function repeatedly, but now each result you get supplies only one of the new arguments you need. A convenient approach is to get the other argument at each step from the successive elements of a list.

Ways to repeatedly apply functions of two arguments.

Here is an example of what (RefLink[FoldList, paclet:ref/FoldList]) does:

FoldList[f,x,{a,b,c}]

(RefLink[Fold, paclet:ref/Fold]) gives the last element of the list produced by (RefLink[FoldList, paclet:ref/FoldList]):

Fold[f,x,{a,b,c}]

This gives a list of cumulative sums:

FoldList[Plus,0,{a,b,c}]

Using (RefLink[Fold, paclet:ref/Fold]) and (RefLink[FoldList, paclet:ref/FoldList]) you can write many elegant and efficient programs in the Wolfram Language. In some cases, you may find it helpful to think of (RefLink[Fold, paclet:ref/Fold]) and (RefLink[FoldList, paclet:ref/FoldList]) as producing a simple nesting of a family of functions indexed by their second argument.

This defines a function nextdigit:

nextdigit[a_,b_]:=10 a+b

This is now like the built-in function (RefLink[FromDigits, paclet:ref/FromDigits]):

fromdigits[digits_]:=Fold[nextdigit,0,digits]

Here is an example of the function in action:

fromdigits[{1,3,7,2,9,1}]