🚀 go-pugleaf

Max Hailperin <max@nic.gac.edu> writes:
>I've got a factorial problem, like maybe
>   6 * 5 * 4 * 3 * 2 * 1.
>
>Gee, I wonder if I can transform that into a simpler problem with the
>same answer.

That's the rabbit.  If you can teach kids to try to transform a problem into
a simpler problem *with the same answer*, why not teach them to notice that
an answer to a simpler problem is part of the answer to this one.

Forcing the simpler problem to have the *same* answer (not just a helpful
answer) makes your recursion come out tail-recursive, which is nice
efficiency but otherwise just a restriction.

How about "I want to know if the word HELLO is somewhere in the tree 
[[HI] [GOOD [BYE FOR [NOW]] [MY [LOVE]]] YOU [SHOULD SAY] [[HELLO]]]"

How do you transform that into a simpler problem with the same answer?  That
kind of thinking is good for some problems but not all problems.

On the other hand, I'm impressed by your chain of thought; it really is a
quite nice way of motivating the tail-recursive solution.

>[Voila, a rabbit!  Is this what you call "boring ... facts to
> memorize"?  I'd call it more like a general problem solving
> heuristic, fit to go into the personal tool-kit right alongside
> 'Gee, I wonder if there is a smaller problem which, if I knew the
>  answer to it, would make it easy to find the answer to this
>  problem?']

Certainly not "boring facts to memorize"!  It is a general problem solving
heuristic.  To my mind, it's just a special case of the second heuristic you
mention, specially tuned up to produce tail recursive programs.  But
nevertheless, stating it the way you did makes it seem more like computer
science and less like an efficiency hack to me.

-Matt