in reply to Re^6: Recursion problem
in thread Recursion problem

I think you can argue both ways.

Okay, Here's my argument for my way :)

If I'm auditing a set of books and need to understand the absence of a cheque to a customer-supplier one month, and go looking for a combination of debits and credits that sum to zero (hence no cheque needed raising), I would not be best pleased if my algorithm came back and told me that "this (empty) set of no credits and no debits could account for that possibility".

Your original code does roughly for both base case and recursive case ...

Actually, that is very deliberate. I try very hard to reduce the number of special cases in recursive algorithms. Recursive nirvana is no special cases, but that is exceptionally rare. In real life even many of the cases that mathematicians treat as having no special cases, eg. succ(n), actually have machine limits.


Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

Replies are listed 'Best First'.
Re^8: Recursion problem
by ysth (Canon) on May 25, 2008 at 20:00 UTC

      It was pointed out that I may have misunderstood your concerns with my first reply. That you were probably alluding to the fact that the code I offered the OP only detects the first possible matching sequence, rather than returning all possible sequences. I attempted to offer the OP a starting point from which to understand how to develop recursive solutions, rather than just hand him a complete solution on a plate.

      That starting point can easily be extended to return the numbers involved in the (first) sequence detected:

      sub sumTo { my $target = shift; for my $i ( 0 .. $#_ ) { return [ $_[ $i ] ] if $_[ $i ] == $target; if( @{ $_ = sumTo( $target - $_[ $i ], @_[ 0 .. $i-1, $i+1 .. $#_ + ] ) } ) { return [ $_[ $i ], @{ $_ } ]; } } return []; }

      And that can be extended to produce all sequences as follows:

      sub sumTo { my $target = shift; return map { $_[ $_ ] == $target ? [ $target ] : do{ my $x = $_[ $_ ]; map { @{ $_ } ? [ $x, @{ $_ } ] : () } sumTo( $target - $x, @_[ 0 .. $_-1, $_+1 .. $#_ ] ); }; } 0 .. $#_; } my @numbers = ( 5, -6, 8, 10, 12, 3, 10 ); print "$ARGV[ 0 ]: sum [@$_] => ", sum( @$_ ) for sumTo( $ARGV[ 0 ], @numbers ); __END__ [ 9:46:47.20] c:\test>688357 21 21: sum [5 -6 10 12] => 21 21: sum [5 -6 12 10] => 21 21: sum [5 -6 12 10] => 21 21: sum [5 -6 10 12] => 21 21: sum [5 10 -6 12] => 21 21: sum [5 10 12 -6] => 21 21: sum [5 12 -6 10] => 21 21: sum [5 12 -6 10] => 21 21: sum [5 12 10 -6] => 21 21: sum [5 12 10 -6] => 21 21: sum [5 10 -6 12] => 21 21: sum [5 10 12 -6] => 21 21: sum [-6 5 10 12] => 21 21: sum [-6 5 12 10] => 21 21: sum [-6 5 12 10] => 21 21: sum [-6 5 10 12] => 21 21: sum [-6 10 5 12] => 21 21: sum [-6 10 12 5] => 21 21: sum [-6 12 5 10] => 21 21: sum [-6 12 5 10] => 21 21: sum [-6 12 10 5] => 21 21: sum [-6 12 10 5] => 21 21: sum [-6 10 5 12] => 21 21: sum [-6 10 12 5] => 21 21: sum [8 10 3] => 21 21: sum [8 3 10] => 21 21: sum [8 3 10] => 21 21: sum [8 10 3] => 21 21: sum [10 5 -6 12] => 21 21: sum [10 5 12 -6] => 21 21: sum [10 -6 5 12] => 21 21: sum [10 -6 12 5] => 21 21: sum [10 8 3] => 21 21: sum [10 12 5 -6] => 21 21: sum [10 12 -6 5] => 21 21: sum [10 3 8] => 21 21: sum [12 5 -6 10] => 21 21: sum [12 5 -6 10] => 21 21: sum [12 5 10 -6] => 21 21: sum [12 5 10 -6] => 21 21: sum [12 -6 5 10] => 21 21: sum [12 -6 5 10] => 21 21: sum [12 -6 10 5] => 21 21: sum [12 -6 10 5] => 21 21: sum [12 10 5 -6] => 21 21: sum [12 10 -6 5] => 21 21: sum [12 10 5 -6] => 21 21: sum [12 10 -6 5] => 21 21: sum [3 8 10] => 21 21: sum [3 8 10] => 21 21: sum [3 10 8] => 21 21: sum [3 10 8] => 21 21: sum [10 5 -6 12] => 21 21: sum [10 5 12 -6] => 21 21: sum [10 -6 5 12] => 21 21: sum [10 -6 12 5] => 21 21: sum [10 8 3] => 21 21: sum [10 12 5 -6] => 21 21: sum [10 12 -6 5] => 21 21: sum [10 3 8] => 21

      Each is a logical progression of the preceeding.


      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
        I was just exploring what felt like a quasi-contradiction in your argument. You seemed to be arguing that the solution of interest would be the first non-empty set, and I had trouble seeing where you'd want both the "non-empty" and the "first" qualifiers.

      All, except the empty set case. Eventually you might need to investigate further to see if one such set was consistant with other information--order and delivery notes etc.--but initially, just whether any such (non-empty) set existed might be a useful boolean. But it would be rendered meaningless if the empty set is considered a match.

      In truth, it was just the first example I thought of that supported my argument. However, hard as I might try, I cannot think of a counter example. Not one.


      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.