Recursive Programming: Merge Lists (Mathematica: Join)

This example shows how to write a merge function in functional programming style using recursion. We take two Lists.

list1=RandomInteger[{1,10},5]
list2=RandomInteger[{-1,-10},7]

{3,10,2,10,3}
{-10,-9,-6,-2,-3,-8,-3}

As Maeder says about the ease and brevity of functional-style programming, it cannot get much simpler than this.

simplestMerge[a_List,b_List]:={a,b}//Flatten;
simplestMerge[list1,list2]

{3,10,2,10,3,-10,-9,-6,-2,-3,-8,-3}

To make it work on an unlimited number of Lists, we follow standard recursion procedure and define two base cases as the first piecewise definitions, then the general recursive function. The base cases will stop the recursion and let the nested recursion list unwind by evaluating from the base case 'outward.'

Use Clear liberally when construction piecewise definitions. To see how a recursive function works, use recursiveFunction//Trace with toy examples. Note that Flatten is a fast (Log@n) operation.

Clear@recursiveMerge;
recursiveMerge@a_List:=a;

recursiveMerge[a_List,b_]:={a,b}//Flatten;

recursiveMerge[a_List,b___List]:=recursiveMerge[a,recursiveMerge@{b}]//Flatten;

We must test it on use-cases.

list3=RandomInteger[{15,20},2]
list4=RandomInteger[{20,25},3]

{18,16}
{22,25,22}

recursiveMerge[list1,4]

{3,10,2,10,3,4}

recursiveMerge[list1,list2]

{3,10,2,10,3,-10,-9,-6,-2,-3,-8,-3}

recursiveMerge[list1,list2,list3]

{3,10,2,10,3,-10,-9,-6,-2,-3,-8,-3,18,16}

recursiveMerge[list1,list2,list3,list4]

{3,10,2,10,3,-10,-9,-6,-2,-3,-8,-3,18,16,22,25,22}

This post follows and expands Wagner Section 5.4.2, Recursion on lists. You cannot do better than these books. Since Wagner is out of print, I shall be posting excerpts to preserve his insights.