Skip to content

NestList

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

NestList[f, expr, n]

gives a list of the results of applying f to expr 0 through n times.

Notes The result is a list of length n+1 whose first element is expr and whose (k+1)-th element is f applied k times to expr. n must be a non-negative integer. f may be a symbol or a pure function; each intermediate application is evaluated before the next one.

Examples (15)

Every input below was run against the current Mathilda build and its output recorded.

Basic examples (11)

In[1]:= NestList[f, x, 4]
Out[1]= {x, f[x], f[f[x]], f[f[f[x]]], f[f[f[f[x]]]]}

In[2]:= NestList[Cos, 1.0, 10]
Out[2]= {1.0, 0.540302, 0.857553, 0.65429, 0.79348, 0.701369, 0.76396, 0.722102, 0.750418, 0.731404, 0.744237}

In[3]:= NestList[(1 + #)^2 &, x, 3]
Out[3]= {x, (1 + x)^2, (1 + (1 + x)^2)^2, (1 + (1 + (1 + x)^2)^2)^2}

In[4]:= NestList[Sqrt, 100.0, 4]
Out[4]= {100.0, 10.0, 3.16228, 1.77828, 1.33352}

In[5]:= NestList[2 # &, 1, 10]
Out[5]= {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024}

In[6]:= NestList[# + 1 &, 0, 10]
Out[6]= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

In[7]:= NestList[#^2 &, 2, 6]
Out[7]= {2, 4, 16, 256, 65536, 4294967296, 18446744073709551616}

In[8]:= NestList[#(1 + 0.05) &, 1000, 10]
Out[8]= {1000, 1050.0, 1102.5, 1157.62, 1215.51, 1276.28, 1340.1, 1407.1, 1477.46, 1551.33, 1628.89}

In[9]:= NestList[(# + 2/#)/2 &, 1.0, 5]
Out[9]= {1.0, 1.5, 1.41667, 1.41422, 1.41421, 1.41421}

In[10]:= NestList[If[EvenQ[#], #/2, (3 # + 1)/2] &, 100, 20]
Out[10]= {100, 50, 25, 38, 19, 29, 44, 22, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1, 2, 1}

In[11]:= NestList[Mod[59 #, 101] &, 1, 15]
Out[11]= {1, 59, 47, 46, 88, 41, 96, 8, 68, 73, 65, 98, 25, 61, 64, 39}

Applications (4)

In[12]:= NestList[f, x, 3]
Out[12]= {x, f[x], f[f[x]], f[f[f[x]]]}

In[13]:= NestList[2 # &, 1, 5]
Out[13]= {1, 2, 4, 8, 16, 32}

In[14]:= NestList[(# + 2/#)/2 &, 1, 4]
Out[14]= {1, 3/2, 17/12, 577/408, 665857/470832}

In[15]:= NestList[1/(1 + #) &, x, 3]
Out[15]= {x, 1/(1 + x), 1/(1 + 1/(1 + x)), 1/(1 + 1/(1 + 1/(1 + x)))}

Implementation notes

builtin_nestlist is nest_impl(res, true): it returns the full iteration history {expr, f[expr], ..., Nest[f,expr,n]}. It seeds an ExprBuf with a copy of expr and runs the shared iter_run driver with nest_step (each step is apply_unary(f, last) = build f[last] and eval_and_free). With as_list=true, ebuf_finalize wraps the entire kept history in a List head. Shares all machinery with Nest; n must be a non-negative integer.

  • Protected.
  • Returns a list of length n + 1 whose first element is expr and whose (k+1)-th element is f applied k times to expr.
  • n must be a non-negative integer; NestList[f, expr, 0] returns {expr}.
  • The function f may be a symbol, a built-in, or a pure function (... &).
  • Each iteration evaluates f[current] before proceeding, so numeric computations collapse immediately.
  • Returns unevaluated if n is not a non-negative integer or the argument count is wrong.
  • Compilable inside Compile[] for a scalar accumulator, with any of the function spellings listed in control-flow.md § Compile. A negative n declines there too, since it is unevaluated here.
  • Last[NestList[f, expr, n]] is equivalent to Nest[f, expr, n].

Attributes: Protected.

References

Notes & additional examples

Notes

NestList[f, expr, n] returns a list of length n + 1: the first element is expr and each subsequent element applies one more f. It is the value-collecting companion of Nest, useful for capturing an entire orbit or sequence (powers of two, a counter, the iterates of a map). n must be a non-negative integer, and each intermediate value is evaluated before being appended.