Applying Functions Repeatedly

Many programs you write will involve operations that need to be iterated several times. Nest and NestList are powerful constructs for doing this.

Nest[f,x,n]apply the function f nested n times to x
NestList[f,x,n]generate the list , where f is nested up to n deep

Applying functions of one argument repeatedly.

Nest[f,x,n] takes the "name" f of a function, and applies the function n times to x.
In[1]:=
Click for copyable input
Out[1]=
This makes a list of each successive nesting.
In[2]:=
Click for copyable input
Out[2]=
Here is a simple function.
In[3]:=
Click for copyable input
You can iterate the function using Nest.
In[4]:=
Click for copyable input
Out[4]=

Nest and 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 FixedPoint and FixedPointList.

FixedPoint[f,x]apply the function f repeatedly until the result no longer changes
FixedPointList[f,x]generate the list , stopping when the elements no longer change

Applying functions until the result no longer changes.

Here is a function that takes one step in Newtons approximation to .
In[5]:=
Click for copyable input
Here are five successive iterates of the function, starting at .
In[6]:=
Click for copyable input
Out[6]=
Using the function FixedPoint, you can automatically continue applying until the result no longer changes.
In[7]:=
Click for copyable input
Out[7]=
Here is the sequence of results.
In[8]:=
Click for copyable input
Out[8]=
NestWhile[f,x,test]apply the function f repeatedly until applying test to the result no longer yields True
NestWhileList[f,x,test]generate the list , stopping when applying test to the result no longer yields True
NestWhile[f,x,test,m], NestWhileList[f,x,test,m]
supply the m most recent results as arguments for test at each step
NestWhile[f,x,test,All], NestWhileList[f,x,test,All]
supply all results so far as arguments for test

Applying functions repeatedly until a test fails.

Here is a function which divides a number by 2.
In[9]:=
Click for copyable input
This repeatedly applies until the result is no longer an even number.
In[10]:=
Click for copyable input
Out[10]=
This repeatedly applies , stopping when two successive results are no longer considered unequal, just as in FixedPointList.
In[11]:=
Click for copyable input
Out[11]=
This goes on until the first time a result that has been seen before reappears.
In[12]:=
Click for copyable input
Out[12]=

Operations such as 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.

FoldList[f,x,{a,b,}]create the list
Fold[f,x,{a,b,}]give the last element of the list produced by FoldList[f,x,{a,b,}]

Ways to repeatedly apply functions of two arguments.

Here is an example of what FoldList does.
In[13]:=
Click for copyable input
Out[13]=
Fold gives the last element of the list produced by FoldList.
In[14]:=
Click for copyable input
Out[14]=
This gives a list of cumulative sums.
In[15]:=
Click for copyable input
Out[15]=

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

This defines a function .
In[16]:=
Click for copyable input
This is now like the builtin function FromDigits.
In[17]:=
Click for copyable input
Here is an example of the function in action.
In[18]:=
Click for copyable input
Out[18]=