Brain going crazy with recursive functions

[Arnaud Delobelle]

5lvqbwl02 at sneakemail.com writes:

> I'm trying to solve the 9-tile puzzle using as functional an approach
> as possible.  I've recently finished reading SICP and am deliberately
> avoiding easy python-isms for the more convoluted scheme/functional
> methods.  The following function is trivial to do with for loops and
> directly accessing arrays with [] syntax.  I'm trying to limit myself
> to the types of idioms/semantics one finds in minimal scheme, such as
> in SICP.  I want eventually to port this to scheme, but I know python
> better, so that's where I'm starting.
>
> My current problem is the following.  The 9-tile puzzle consists of a
> list of lists like this [[1,2,3],[4,5,6],[7,8,0]], where the numbers
> can be jumbled up.  I'm looking for the location of the zero using
> *only* recursion and operators that are similar to car/cdr.  The
> return value should be the row,col of the zero.  For example above
> the
> return value would be (2,2).

I'm not sure what your code does but there is a canonical way to
transform a loop the call of a recursive function.  I don't think I can
put it into words easily so I've demonstrated it
below on your 'locate_zero' function.

def find_zero(square):
    "The normal imperative way in simple Python."
    i = 0
    for row in square:
        j = 0
        for n in row:
            if n == 0:
                return i, j
            j += 1
        i += 1

def func_find_zero(square):
    """
    The translation into recursive calls. A function is created for
    each loop.  There are no mutations.
    """
    def square_loop(square, i):
        def row_loop(row, j):
            if row:
                if row[0] == 0:
                    return i, j
                else:
                    return row_loop(row[1:], j+1)
        if square:
            res = row_loop(square[0], 0)
            if res is not None:
                return res
            else:
                return square_loop(square[1:], i+1)
    return square_loop(square, 0)

I've intentionally made both function 'non-clever' to make the translation
process more apparent.

-- 
Arnaud