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:

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.


4 Answers 4


You were pretty close.

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

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}, {}]]
  • 2
    $\begingroup$ 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]], {}] $\endgroup$ Jun 7, 2013 at 2:25
  • 1
    $\begingroup$ @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). $\endgroup$
    – kale
    Jun 7, 2013 at 13:26
  • 1
    $\begingroup$ @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. $\endgroup$
    – kale
    Jun 7, 2013 at 15:13
  • 1
    $\begingroup$ @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. $\endgroup$ Jun 7, 2013 at 15:17
  • 2
    $\begingroup$ @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. $\endgroup$ Jun 7, 2013 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

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.

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).

  • $\begingroup$ 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. :-) $\endgroup$
    – Clif
    Jun 7, 2013 at 14:25
  • 1
    $\begingroup$ @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. $\endgroup$ Jun 7, 2013 at 15:13
  • $\begingroup$ 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. $\endgroup$
    – Clif
    Jun 7, 2013 at 15:43
  • 1
    $\begingroup$ @Clif Yes, that's the one. $\endgroup$ Jun 7, 2013 at 15:46
part[l_List, n_] := Module[{p},
  p[{f : Repeated[_, {n}], rest___}] := Sequence[{f}, p[{rest}]];
  p[{Repeated[_, n-1]}] := Sequence[];

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]]
  • $\begingroup$ What happened if you try part[{1, 2, 3, 4, 5}, 2]? $\endgroup$
    – Silvia
    Jun 7, 2013 at 3:56
  • $\begingroup$ Hey @Silvia! I'm afraid to try. But I assumed the truncation and argument checking weren't part of the OP's doubts $\endgroup$
    – Rojo
    Jun 7, 2013 at 3:58
  • 1
    $\begingroup$ I'm just +1 and saying :D Maybe p[f : Repeated[_, n - 1]] := Sequence[]? $\endgroup$
    – Silvia
    Jun 7, 2013 at 4:01
  • $\begingroup$ There we go @Silvia. Don't try a negative n ;D $\endgroup$
    – Rojo
    Jun 7, 2013 at 4:10
  • 1
    $\begingroup$ @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 $\endgroup$
    – Rojo
    Jun 7, 2013 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.