Re^2: Mark Jason Dominus And Me - The Partition Problem

[Tommy]

Wow, thanks tilly. I really appreciate your taking time to look at my meditation and read my code. I'd like to respond to a few of the things you said, and mostly in the form of questions (if you don't mind)

You said:

"If you got through the Fibonacci and directory walk examples then you obviously understand the principle of recursion. Why would you balk on this example? My most likely guess is that you try to visualize what is happening. In the case of Fibonacci it is easy enough to verify, number by number, what is happening. In the case of a directory walk, it is easy enough to visualize what it is doing, and see how it works."

YES, exactly. I can confidently say that I know what recursion is, and more importantly I'd like to believe that I "understand" recursion; the directory walk is a piece of cake (I've written very similar code in the past), and the Fibonacci exercise was also very easy to grasp. I could easily see where/why the code recursed and when/what it returned.

The two things I don't understand:

1.) Why the ambiguous output?

My confusion lies in the final 3 lines of the output of my (more verbose) version of the MJD recursive solution, as shown in the original post. I don't understand why something that appears to be a partial answer gets passed back up the stack and marked as a "solution", per the "$solution" variable name taken from the MJD code. When the code claims to have found a solution the first time, the solution it finds is not the real solution to the problem. Only higher on up the stack is the real solution identified. The first claim to have found a solution doesn't ring true. Sub-question: What made this solution work then?

2.) When is recursion the right thing to do?

What criteria make recursion the method of choice for approaching problems as opposed to iteration? For a predefined tree structure, the answer is obvious, however I don't see why it is the only way to accomplish the solution of the Partition Problem which has no pre-defined tree that I can see. I don't doubt your assertion that recursion is the correct methodology for finding a solution to the Partition Problem, but could you tell me why? How would I recognize that I needed recursion there?

I had to jot this down quickly before taking the kids to school and going to $work, so please forgive me if there's any muddled grammar or disjointed sentences...

[tilly]

For 1 the trick is in the first recursive call. When we subtract the current treasure from the target, we want to find solutions that include the current treasure. However inside that call, we don't know about the existence of that current treasure on the inner call - that fact is implicit in the fact that the target is smaller, and it will only get added back to the solution after the inner call returns.

For 2 the answer is, "Whenever we have a problem that we don't know how to solve, which can be somehow reduced to simpler versions of the same problem." For Fibonacci, that means smaller $n. In the case of the directory walk, that means farther down the directory tree. In the case of the partition problem, simpler means "fewer treasures".

[Tommy]

Ummm. Just doesn't make sense to me to try and hit a moving $target... pun intended. It makes a helluva lot more sense now that my target stays constant and my "share" is the only thing really changing (see code below).

Thank you tilly for helping me understand why I didn't understand. That's when everything started making sense.

NEW CODE

This is how I would do it... (remove "print" statements after debugging done).

#!/usr/bin/perl

use strict;
use warnings;

my ( $target, @treasures, $calls );

$target = shift @ARGV || 7;
@treasures = @ARGV;
@treasures = ( 2, 3, 4, 5, 1 ) unless @treasures;

sub find_share
{
   my ( $trial_set, $avail_choices, $depth ) = @_;

   $depth ||= 0; $depth += 1;

   $calls++;

   my $ts_total = 0;

   $ts_total += $_ for @$trial_set;

   printf qq{%-8s Call %-5d Depth: %-5d Trial set: %-10s Remaining: %-
+16s ... },
      ( '-' x $depth ) . '>',
      $calls,
      $depth,
      "[ @$trial_set ]",
      "[ @$avail_choices ]";

   print qq{Found solution: [ @$trial_set ] == $target\n\n}
      and return $trial_set if $ts_total == $target;

   print qq{Returning undef because trial set total $ts_total > $targe
+t\n}
      and return undef if $ts_total > $target;

   print qq{Returning undef because no available choices remain } .
         qq{and $ts_total < $target\n}
            and return undef if @$avail_choices == 0;

   my ( @my_trial_set ) = @$trial_set;
   my ( @my_avail_choices ) = @$avail_choices;

   push @my_trial_set, shift @my_avail_choices;

   print qq{$ts_total < $target, so I put "$my_trial_set[-1]" } .
         qq{into the trial set, and now I'll recurse\n};

   my $solution = find_share( \@my_trial_set, \@my_avail_choices, $dep
+th );

   print +( '-' x $depth ) . '>',
      qq(A recursive call at depth @{[ $depth + 1 ]} found that a solu
+tion } ) .
      qq(of [ @$solution ] adds up to my target of $target at depth $d
+epth\n)
         and return [ @$solution ] if $solution;

   print '-' x $depth, '> ',
      qq{Situation failed.  Omitting treasure [ $my_trial_set[-1] ] an
+d } .
      qq{backtracking to choices of [ @my_avail_choices ] at depth $de
+pth\n\n};

   pop @my_trial_set;

   return find_share( \@my_trial_set, \@my_avail_choices, $depth );
}

print qq{Trying to hit target of $target...\n\n}; print <<__ANS__;

Solution: [ @{ find_share( [], \@treasures ) || [ "no solution possibl
+e" ] } ]

__ANS__

exit;

__END__

   DING!  That moment when...

    \   |   /
      _---_
  \  /     \  /
__  |       | __
     \ 8-8 /
  /   \l_l/  \
       ===
       =u=

   ...the light comes on and you get it.

OUTPUT

Click "Download code" link to see the actual, pretty, wide-formatted text

$ perl find_shares_myway_2.pl
Trying to hit target of 7...

->       Call 1     Depth: 1     Trial set: [  ]       Remaining: [ 2 
+3 4 5 1 ]    ... 0 < 7, so I put "2" into the trial set, and now I'll
+ recurse
-->      Call 2     Depth: 2     Trial set: [ 2 ]      Remaining: [ 3 
+4 5 1 ]      ... 2 < 7, so I put "3" into the trial set, and now I'll
+ recurse
--->     Call 3     Depth: 3     Trial set: [ 2 3 ]    Remaining: [ 4 
+5 1 ]        ... 5 < 7, so I put "4" into the trial set, and now I'll
+ recurse
---->    Call 4     Depth: 4     Trial set: [ 2 3 4 ]  Remaining: [ 5 
+1 ]          ... Returning undef because trial set total 9 > 7
---> Situation failed.  Omitting treasure [ 4 ] and backtracking to ch
+oices of [ 5 1 ] at depth 3

---->    Call 5     Depth: 4     Trial set: [ 2 3 ]    Remaining: [ 5 
+1 ]          ... 5 < 7, so I put "5" into the trial set, and now I'll
+ recurse
----->   Call 6     Depth: 5     Trial set: [ 2 3 5 ]  Remaining: [ 1 
+]            ... Returning undef because trial set total 10 > 7
----> Situation failed.  Omitting treasure [ 5 ] and backtracking to c
+hoices of [ 1 ] at depth 4

----->   Call 7     Depth: 5     Trial set: [ 2 3 ]    Remaining: [ 1 
+]            ... 5 < 7, so I put "1" into the trial set, and now I'll
+ recurse
------>  Call 8     Depth: 6     Trial set: [ 2 3 1 ]  Remaining: [  ]
+             ... Returning undef because no available choices remain 
+and 6 < 7
-----> Situation failed.  Omitting treasure [ 1 ] and backtracking to 
+choices of [  ] at depth 5

------>  Call 9     Depth: 6     Trial set: [ 2 3 ]    Remaining: [  ]
+             ... Returning undef because no available choices remain 
+and 5 < 7
--> Situation failed.  Omitting treasure [ 3 ] and backtracking to cho
+ices of [ 4 5 1 ] at depth 2

--->     Call 10    Depth: 3     Trial set: [ 2 ]      Remaining: [ 4 
+5 1 ]        ... 2 < 7, so I put "4" into the trial set, and now I'll
+ recurse
---->    Call 11    Depth: 4     Trial set: [ 2 4 ]    Remaining: [ 5 
+1 ]          ... 6 < 7, so I put "5" into the trial set, and now I'll
+ recurse
----->   Call 12    Depth: 5     Trial set: [ 2 4 5 ]  Remaining: [ 1 
+]            ... Returning undef because trial set total 11 > 7
----> Situation failed.  Omitting treasure [ 5 ] and backtracking to c
+hoices of [ 1 ] at depth 4

----->   Call 13    Depth: 5     Trial set: [ 2 4 ]    Remaining: [ 1 
+]            ... 6 < 7, so I put "1" into the trial set, and now I'll
+ recurse
------>  Call 14    Depth: 6     Trial set: [ 2 4 1 ]  Remaining: [  ]
+             ... Found solution: [ 2 4 1 ] == 7

----->A recursive call at depth 6 found that a solution } of [ 2 4 1 ]
+ adds up to my target of 7 at depth 5
--->A recursive call at depth 4 found that a solution } of [ 2 4 1 ] a
+dds up to my target of 7 at depth 3
->A recursive call at depth 2 found that a solution } of [ 2 4 1 ] add
+s up to my target of 7 at depth 1

Solution: [ 2 4 1 ]

[Tommy]

INTERESTING!

Maybe it doesn't hurt to program the way your brain really thinks...at least not this time. You see, I stripped down the MJD code to its barest form, exactly from the book. Then I removed the print statements from my own version which was just shared in the node previous to this node.

Surprise: despite the fact that I'm passing around a reference to my "$share" with each call, my code benches twice as fast. I'm betting it's because I'm not constantly recalculating the "$target".

Anyway, here's the benchmarks. I wonder what conclusions could be drawn. If I cared more, I'd run it through Devel::NYTprof and find out what's really going on and why it's faster to do it the way that makes the most sense to my dyslexic brain:

$ perl ./find_shares_myway_2.pl
Benchmark: timing 500000 iterations of test1...
     test1: 16 wallclock secs (15.43 usr +  0.00 sys = 15.43 CPU) @ 32
+404.41/s (n=500000)
$VAR1 = {
          'test1' => bless( [
                              16,
                              '15.43',
                              0,
                              0,
                              0,
                              500000
                            ], 'Benchmark' )
        };


$ perl ./find_shares.pl
Benchmark: timing 500000 iterations of test1...
     test1: 31 wallclock secs (30.10 usr +  0.02 sys = 30.12 CPU) @ 16
+600.27/s (n=500000)
$VAR1 = {
          'test1' => bless( [
                              31,
                              '30.1',
                              '0.02',
                              0,
                              0,
                              500000
                            ], 'Benchmark' )
        };

[Laurent_R]

Just an additional point. When you'll go further down into MJD's brilliant Higher Order Perl, you'll find out that he warns about problems about recursion (paragraph 1.8, "Where Recursion Blows"), in which he revisits the Fibonacci and Partition problems for larger Fibonacci numbers or larger collections of treasures) and that, later in the book, he is spending quite a bit of time on methods to get rid of recursion (especially Chapter 5, "From Recursion To Iterators, but not only there).

Recursion is a beautiful model not only when you have a predefined tree structure (such as the directory walk example), but also when a problem is very complicated, you often need to reduce it to a collection of smaller or simpler problems, and possibly again and again, until the individual problems become (almost) trivial (this is what divide and conquer algorithms are about). As an example, some of the efficient sort algorithms just do that, although their actual implementation may well have no recursive call at all. You may also want to use recursion if you want to generate all subsets of a set, or combinations or permutations. This may seem to be maths, but it is quite commonly necessary in software engineering. Many of the Operational Research problems also often fall into the category of candidates for recursion.

In brief, recursion gives you a very powerful tool to modeling complex problems, especially when you want to make sure that you have examined absolutely all possibilities. The downside is that, sometimes, recursion will let you visit each possibility a number of times, possibly a huge number of times (there are some ways around that to a certain extent, one of them being caching, which MJD examines in some depth, but not always). So, sometimes you use recursion to better understand the problem and how to solve it, but then change it to iteration or something else when is comes to actual implementation. In such cases, recursion can be thought of as a prototype.

Reading further MJD's book, you will also find out that even for directory walk, recursion is not necessarily the best solution, the reason being that recursion is very good at depth-first traversing of the directory tree; but sometimes you need to traverse the tree in breadth-first order (or some other order), and then, recursion becomes very unpractical to use.

Keep reading this excellent book. I really did not have any problem with recursion when I first read it, but I learned an awful lot of other things from it, and there are other with which I am still fighting after having read them three times. There are some chapters that I will probably read for the fourth time, because I haven't fully understood their full implications and I still have quite a but to learn for them.

[Dominus]

> (paragraph 1.8, "Where Recursion Blows")

I wish I had thought to make that the title.

[Laurent_R]

OK, I missed a word, sorry about that. And English not being my mother tongue, I did not realize that it might sound as a profanity before reading your comment.

[tilly]

Indeed. People who only know how to traverse a directory using recursion will suffer grief if they are asked to do it breadth-first instead. Recursion gives you an implicit stack. If you can unwind it to get an explicit stack instead, then switching between depth-first and breadth-first is as simple as switching from a stack to a queue.

But, one step at a time. Recursion is a great technique for thinking through a problem that you don't know how solve up front. Once you understand that solution, you can start trying to think of other approaches with other trade-offs. :-)

[Anonymous Monk]

could you tell me why? How would I recognize that I needed recursion there?

If you have a set, that you need to divide, you you probably need recursion

See Recursion (computer science) and Divide and conquer algorithm