# Partitioning a list by recursion (Programming Paradigms via Mathematica (A First Course))

I am working through the course Programming Paradigms via Mathematica. One of the homework exercises for the section Recursion I: Passing the Buck is as follows:

Use recursion to partition a list: "recurPartition[L_List,k_Integer]" should return the same thing as "Partition[L,k]". Of course, don't use "Partition[]".

The following additional limitations are also applied:

First, use of a repetition function ("Map[]", "MapThread[]", "Nest[]", "NestList[]", "Fold[]", "FoldList[]", "Table[]", "Apply[]", and so on, being our "adverbs") will generally disqualify a method as purely recursive, for the repetition is accomplished externally from the nested function calls. Also, repetition accomplished with a loop structure, such as a "While[]", a "Do[]", or some other repetition command, is explicitly forbidden.

Here was my code, following many edits:

Clear[recurPartition]
recurPartition[{}, k_] := {}
recurPartition[L_List, k_Integer] :=
If[Length[L] >= k, {Take[L, k], recurPartition[Drop[L, k], k]}]
recurPartition[{1, 2, 3, 4, 5, 6}, 2]


Which produced the following output:

{{1, 2}, {{3, 4}, {{5, 6}, {}}}}

By contrast Partition[{1, 2, 3, 4, 5, 6}, 2] would produce:

{{1, 2}, {3, 4}, {5, 6}}

I can't figure out what I should have done differently and would appreciate some guidance.

-

You were pretty close.

Here's what I have sticking to your basic construct.

Clear[recurPartition]
recurPartition[l_List, k_Integer] :=
If[Length[l] >= k, Join[{Take[l, k]}, recurPartition[Drop[l, k], k]]]

recurPartition[{1, 2, 3, 4, 5, 6}, 2]


{{1, 2}, {3, 4}, {5, 6}}

Your condition Length[l] >= k is your terminating condition.

To use a function downvalue as the terminating condition, you can use:

recurPartition[l_List, k_Integer] /; k > Length@l := {}
recurPartition[l_List, k_Integer] := Join[{Take[l, k]}, recurPartition[Drop[l, k], k]]


And here's a one-line, J.M.-inspired version:

recurPartition[l_List, k_Integer?Positive, remainderQ_:False] :=
If[Length@l >= k, {l~Take~k}~Join~recurPartition[l~Drop~k, k, remainderQ],
If[remainderQ, {l}, {}]]

-
One-liner: recurPartition[L_List, k_Integer?Positive] /; Mod[Length[L], k] == 0 := If[Length[L] >= k, Join[{Take[L, k]}, recurPartition[Drop[L, k], k]], {}] –  Guess who it is. Jun 7 '13 at 2:25
@Clif, Technically, your terminating condition recurPartition[{}, k_] := {} is never used because of the condition in the If statement. In your example, you don't seem to be interested in "remainder" elements (when the length of the list isn't a multiple of the partition size), so the If statement works fine. (see edit). –  kale Jun 7 '13 at 13:26
@Clif, Thanks for the accept. Leonid always has great solutions (even though he did use Fold & Map :) ). As far as your comment on Leonid's solution, the last version I gave you has the option to keep the "remainder" items, although it still won't outperform on a speed basis. –  kale Jun 7 '13 at 15:13
@Clif Just a side note: built-in Partition will be much faster than any top-level code we might come up with, particularly on numerical (packed) arrays. So, in this case, this is just an instructive exercise. But there are cases where top-level code can be quite fast even compared to built-ins, although they are admittedly less common. –  Leonid Shifrin Jun 7 '13 at 15:17
@Clif The more important thing here is that most posted solutions are not tail-recursive, which limits them severely, because it is quite easy to overflow the stack. In Mathematica, this will lead to a silent kernel crash, with all the possible unwanted consequences such as loss of work and data. All versions above could be made tail-recursive if the result gets accumulated in a separate argument to the recurPartition function. –  Leonid Shifrin Jun 7 '13 at 15:20

As I attempted to explain here, recursion on lists is more involved in Mathematica than it may seem, in part because lists are implemented as arrays (rather than linked lists) in Mathematica.

What I will suggest here is again a solution based on linked lists. It may be a bit harder to understand initially, but arguably it is closer to the true spirit of recursion. It will also be faster than many of the posted answers, and be tail-recursive in the Mathematica sense.

Here is the code

ClearAll[ll];
SetAttributes[ll, HoldAllComplete];
toLinkedList[l_List] := Fold[ll[#2, #1] &, ll[], Reverse@l]


The main function will use two linked lists for accumulation of intermediate results, and one linked list for the input data. Partitioned chunks will be collected into linked lists with the head List, while the elements inside individual chunks will be collected into linked lists with head ll.

ClearAll[partitionLL];
partitionLL[l_List, k_] :=
Block[{\$IterationLimit = Infinity},
partitionLL[toLinkedList[l], k, {}, k - 1]
];
partitionLL[ll[], k_, accum_, n_] :=
Map[List @@ Flatten[#, Infinity, ll] &, Flatten[accum]];
partitionLL[ll[head_, tail_], k_, accum_, n_] /; n == k - 1 :=
partitionLL[tail, k, {accum, ll[ll[], head]}, 0];
partitionLL[ll[head_, tail_], k_, {accum_, current_ll}, n_] :=
partitionLL[tail, k, {accum, ll[current, head]}, n + 1];


The two-argument form of the function converts the initial list into a linked list. After that, the real recursive part has 4 arguments. The recursion stops when the input list is an empty list ll[] - it then converts the list of accumulated results back to a normal list. The other two definitions implement the general recursive step. The first one creates a new partitioned chunk, the last one fills the existing partitioned chunk with a current head of the input list.

Here is a simple example:

partitionLL[Range[10], 2]

(* {{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}}  *)


Here is a more serious test:

partitionLL[Range[20000], 2]; // AbsoluteTiming

(* {0.118164, Null} *)


Note that recursive solutions not using linked lists will generally be slower for large lists because of sub-list copying on every iteration. Note also that one needs to take a special care to make the solution tail-recursive, to make it of any practical use (in the case of functions like Partition, at least).

-
The links to your previous answers are very informative, and the results of your code are indeed impressive, as they outdo (to my way of thinking) Partition in that where Partition[Range[3],2] yields {{1, 2}} your code produces {{1,2},{3}} which to me is a superior result, however I will have to say that the course question gave the qualifier, "the same thing as Partition[L,k]", and your code, while superior, doesn't. As far as your serious test of time, my code set off so many error messages and ran so much slower that I really don't want to compare. :-) –  Clif Jun 7 '13 at 14:25
@Clif Thanks. Re: Partition - there is an extended syntax for Partition which would not dismiss the left-over too. And one can also modify my code above to go the other way around and dismiss the left-over - this should not be hard. Re: speed comparison - I meant not just your code but most of the posted solutions that were using plain lists. –  Leonid Shifrin Jun 7 '13 at 15:13
is Partition[Range[21], 2, 2, 1, {}] an example of what you are talking about? I had missed that while looking over what Partition does, thanks for bringing that to my attention. –  Clif Jun 7 '13 at 15:43
@Clif Yes, that's the one. –  Leonid Shifrin Jun 7 '13 at 15:46
part[l_List, n_] := Module[{p},
p[{f : Repeated[_, {n}], rest___}] := Sequence[{f}, p[{rest}]];
p[{Repeated[_, n-1]}] := Sequence[];
{p[l]}
]


but probably something along the lines of halirutan's solution is more appropriate

part2[l_List, n_] := part2[l, n, {}];
part2[l_List, n_, res_]/;Length@l<n := res;
part2[l_, n_, curr_] := part2[l~Drop~n, n, Append[curr, l~Take~n]]

-
What happened if you try part[{1, 2, 3, 4, 5}, 2]? –  Silvia Jun 7 '13 at 3:56
Hey @Silvia! I'm afraid to try. But I assumed the truncation and argument checking weren't part of the OP's doubts –  Rojo Jun 7 '13 at 3:58
I'm just +1 and saying :D Maybe p[f : Repeated[_, n - 1]] := Sequence[]? –  Silvia Jun 7 '13 at 4:01
There we go @Silvia. Don't try a negative n ;D –  Rojo Jun 7 '13 at 4:10
@Clif, I hoped it would be an educational example. But it shouldn't be very efficient. In fact, it would make the Leonids die a little inside –  Rojo Jun 7 '13 at 19:13

Here an implementation which emulates the Take by recursion too

rp[l_, k_?Positive] := rp[l, {}, k, k] /; Length[l] >= k;
rp[l1_, l2_, k_, iter_] := rp[Rest[l1], Append[l2, First[l1]], k, iter - 1];
rp[l1_, l2_, k_, 0] := Join[{l2}, rp[l1, k]];
rp[__] := {};


The trick is that you have two different recursions through two different call patterns although the functions name is rp in all cases. I hope it works, it's pretty late here.

-
Thank you for the code, it works very well, and I can see where adding the ?Positive restriction to k_ is good programing procedure. –  Clif Jun 7 '13 at 13:25