Recursive Programming on Lists (Arrays): Map

Here is a simple recursive mapping function. This is a recursion on Lists (arrays) with arbitrary argument types, not numbers.

Recall that Map is a classic functional-style, 'structural' command since it leads us to think in terms of applying a function to an entire structure, such as an array (a List in Mathematica). The Map function saves us the trouble of 'deconstructing' the array with a Do or For loop as in procedural programming.

We define a base case and a recursive case:

1. Base case: If the source List is empty, just return it

2. Recursive case: Call itself on the Rest of each successively smaller sub-List

Clear@recursiveMap;
recursiveMap[function_,aList_List]:=
If[aList=={},{},
Prepend[recursiveMap[function,Rest@aList],function@First@aList]]

We test the base case:

recursiveMap[f,{}]

{}

We test some recursive cases:

recursiveMap[f,{a,b,c}]

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

recursiveMap[f,Range@5]

{f[1],f[2],f[3],f[4],f[5]}

How does it work? You can go through the Trace, but essentially by calling itself repeatedly on the Rest of list (via the first, recursive 'clause' of recursiveMap, recursiveMap[function,Rest@list]), it constructs successively smaller sub-Lists and eventually hits the empty List, which is the base case. 

Then it begins 'unwinding' and Prepend and the second clause of recursiveMap is repeatedly invoked (function@First@list). Starting with the last List of a single element (c in this Trace), it applies the function f to the First element of each sub-List and Prepends it to a growing List of results until the First element of the entire list is Prepended.

Trace@recursiveMap[f,{a,b,c}]

{recursiveMap[f,{a,b,c}],If[{a,b,c}=={},{},Prepend[recursiveMap[f,Rest[{a,b,c}]],f[First[{a,b,c}]]]],{{a,b,c}=={},False},If[False,{},Prepend[recursiveMap[f,Rest[{a,b,c}]],f[First[{a,b,c}]]]],Prepend[recursiveMap[f,Rest[{a,b,c}]],f[First[{a,b,c}]]],{{Rest[{a,b,c}],{b,c}},recursiveMap[f,{b,c}],If[{b,c}=={},{},Prepend[recursiveMap[f,Rest[{b,c}]],f[First[{b,c}]]]],{{b,c}=={},False},If[False,{},Prepend[recursiveMap[f,Rest[{b,c}]],f[First[{b,c}]]]],Prepend[recursiveMap[f,Rest[{b,c}]],f[First[{b,c}]]],{{Rest[{b,c}],{c}},recursiveMap[f,{c}],If[{c}=={},{},Prepend[recursiveMap[f,Rest[{c}]],f[First[{c}]]]],{{c}=={},False},If[False,{},Prepend[recursiveMap[f,Rest[{c}]],f[First[{c}]]]],Prepend[recursiveMap[f,Rest[{c}]],f[First[{c}]]],{{Rest[{c}],{}},recursiveMap[f,{}],If[{}=={},{},Prepend[recursiveMap[f,Rest[{}]],f[First[{}]]]],{{}=={},True},If[True,{},Prepend[recursiveMap[f,Rest[{}]],f[First[{}]]]],{}},{{First[{c}],c},f[c]},Prepend[{},f[c]],{f[c]}},{{First[{b,c}],b},f[b]},Prepend[{f[c]},f[b]],{f[b],f[c]}},{{First[{a,b,c}],a},f[a]},Prepend[{f[b],f[c]},f[a]],{f[a],f[b],f[c]}}

Source: David Wagner

Using Recursion to Define a Periodic Function

I'm working my way through Heikki Ruskeepaa's book, Mathematica Navigator and found this elegant one-liner that shows how to define a periodic function with recursion. Note that the base case required to stop the recursion is not a single value but the condition 0 <= t <= 2.

Clear@sawtooth;sawtooth[time_,scale_:1]:=If[0<=time<=2,scale time,sawtooth[scale (time-2)]]
Plot[sawtooth@t,{t,0,10}]

How does the recursion work? If t => 2, sawtooth keeps subtracting 2 from t recursively until t is back in the range 0 <= t <= 2 and computes that value for y. We can see sample values of a function plotted with DiscretePlot.

DiscretePlot[sawtooth@t,{t,0,6,0.2},PlotTheme->"Web"]

Of course a faster way of defining the domain is to use Mod, but there is a lesson here. We don't need the speed of Mod, so either implementation is fine - using Mod for the most compact and fast function, or using an elegant new recursive technique to learn it. This function omits the values at multiples of 2, but is effectively the same function:

Clear@sawtooth2;sawtooth2[time_,scale_:1]:=scale Mod[time,2]

Mathematica has built-in functions to produce various canonical waveforms  such as SawtoothWave. Here are square and triangular wave examples.

Plot[SquareWave[{-50,50},t],{t,0,10},ExclusionsStyle->Dotted,AxesLabel->{"time (mS)","mV"},PlotLabel->"Electric potential at the electrode"]

Plot[TriangleWave[{-40,10},t],{t,0,10},AxesLabel->{"time (mS)","mV"},PlotLabel->"Electric potential seen by the axon"]

Examples of Different Programming Styles with Timing

This comparison of different programming styles is adapted from Roman Maeder's in his Programming in Mathematica course. Here is a List of expressions to square, including different types on numbers and an undefined symbol.

alist={a,1.1,2+3I,4,573297329847};

Functional Style

Here is the shortest solution, which works due to the function Attribute, Listable, of Power that maps Power over a List. You can add Listable to your own functions to achieve the same simplicity.

squareListListable@list_List:=list^2

squareListListable@alist
{a^2,1.21,-5+12 I,16,328669828409699917043409}

As Maeder says, it really cannot get much simpler than that. Here are two more functional-style solution. These are also compact. The first uses Table, a very powerful function that leads us to not deconstruct lists (arrays) but to think of applying a function to them as a whole. The simple squaring of each List item could be replaced with a function of arbitrary complexity.

squareFunctional@list_List:=Table[i^2,{i,list}]

Beginners are often unaware of Table's ability to iterate directly over List items, as above, without this unnecessary clutter. However, see the Timing analysis below for a surprise.

squareFunctionalWithIterator@list_List:=Table[list[[i]]^2,{i,Length@list}]

This third functional example uses Map, another powerful function that, along with Listable and Table, replaces the Do loop. A pure Function expresses the squaring operation concisely.

squareListMapped@list_List:=Map[#^2&,list]

Rule-Based Style

Programming with replacement rules is the way Mathematica itself works — Every Change is a Transformation — and rule-based functions are often very concise and easy to understand. I prefer rule-based functions over other styles.

squareRuleBasedShorter@list_List:=list/.{first___,x_,rest___}->{first,x^2,rest}

Recursive Style

Here is a recursive rule-based approach — the function calls itself and keeps marching down a 'rest' of List that keeps getting smaller. Note that flattening deeply nested Lists is a very fast operation (Log@n) whose timing you rarely need to worry about. However this recursive approach is only practical for small examples.

squareRuleRecursive@list_List:=list/.{x_,rest___}:>{x^2,squareRuleRecursive@{rest}}//Flatten

Procedural Style

While I really think which style to use is a personal decision ('de gustibus non est disputandum'), this procedural solution does seem cumbersome and old-fashioned compared to the functional and rule-based ones. But sometimes procedural functions are easier and faster to write than laboring to find more concise functional or rule-based ones.

squareProcedural@list_List:=Module[{array1={},squaresList,
listLength=Length@list},
Do[array1=Prepend[array1,0],{i,listLength}];
Do[array1[[i]]=list[[i]]^2,{i,listLength}];
Return@array1
]

Maeder cheats a bit, using Table to initialize his array, which speeds up his function considerably as you'll see in the Timing analysis.

squareProceduralMaeder@list_List:=Module[
{squaresArray,
listLength=Length@list},
(*initialize the array*)
squaresArray=Table[0,{listLength}];
Do[squaresArray[[i]]=list[[i]]^2,{i,listLength}];
Return@squaresArray
]

Timing Analysis

aLongList=Range[10^6];

The Listable function is the clear winner.

Timing[squareListListable@aLongList;]
{0.,Null}

Let's push it harder to see more of its speed advantage. It appears to be 10 times faster than its competitors below.

Timing[squareListListable@Range[10^7];]
{0.015600,Null}

Timing[squareFunctional@aLongList;]
{0.031200,Null}

Here's the surprise I mentioned. Not sure why, but using the iterator is exactly twice as fast than 'directly' iterating over List items. I'd only worry about this for functions needing optimization though.

Timing[squareFunctionalWithIterator@aLongList;]
{0.015600,Null}

Timing[squareListMapped@aLongList;]
{0.015600,Null}

It surprise me that the rule-based approach is relatively slow.

Timing[squareRuleBased@aLongList;]
{0.062400,Null}

Both the recursive and procedural approaches are very slow.

Timing[squareRuleRecursive@aLongList;]
During evaluation of In[186]:= $RecursionLimit::reclim: Recursion depth of 1024 exceeded. >>
Out[186]= {9.188459,Null}

Timing[squareProcedural@aLongList;]
$Aborted

Timing[squareProceduralMaeder@aLongList;]

{2.012413,Null}