Recursion head scratcher

Tim Wintle tim.wintle at teamrubber.com
Wed Dec 2 02:53:51 EST 2009


On Wed, 2009-12-02 at 02:07 -0500, Joel Madigan wrote:
> 
> that it is possible to make it print the path to the finish in the
> order the steps were taken.  That is, the algorithm as written
> produces: (4,0) (4,1) (3,1) (3,2) (3,3) (2,3) (1,3) (1,2) True 
> 
> Rather than (1,2) (1,3) (2,3) (3,3) (3,2) (3,1) (4,1) (4,0) True 
> 
> Furthermore, he claims it's a "one line change" without using a stack
> or any other extra data structure

The way I see immediately is a three line change (if you include
modifying/removing the existing print statements). It will be one line
shorter to print the other order.

As a hint - think of what the python interpreter's stack looks like when
it's running your code at the moment - that's the stack you're currently
using (and need to use) to store the results you print.

Tim




More information about the Python-list mailing list