From: Geoffrey King
Subject: method vs function recursion
Date: Sat, 19 Nov 2005 08:27:18 +0000
Message-ID: <437ee1e3$0$26311$afc38c87@news.optusnet.com.au>

Any suggestions...

I was surprised when I converted my flood-fill from a defun to a 
defmethod and got a stack overflow (16000).

Is the recursive defmethod so much more expensive or is it more likely 
that it is some sort of user (me) error?

If it matters the game-map object is not light weight.

The relevant code snippets are:

(defmethod flood-fill2 ((this game-map) (x integer) (y integer))
   (when (not (equal "+" (grid-get-at this x y)))
     (grid-put-at this x y "+")
     (flood-fill2 this x (1- y))
     (flood-fill2 this x (1+ y))
     (flood-fill2 this (1- x) y)
     (flood-fill2 this (1+ x) y)))

(defun flood-fill (this x y)
   (when (not (equal "+" (grid-get-at this x y)))
     (grid-put-at this x y "+")
     (flood-fill this x (1- y))
     (flood-fill this x (1+ y))
     (flood-fill this (1- x) y)
     (flood-fill this (1+ x) y)))

• Re: method vs function recursion Pascal Costanza
  • Re: method vs function recursion verec

From: Pascal Costanza
Subject: Re: method vs function recursion
Date: Sat, 19 Nov 2005 09:21:32 +0000
Message-ID: <3u894sFuroi6U1@individual.net>

Geoffrey King wrote:
> Any suggestions...
> 
> I was surprised when I converted my flood-fill from a defun to a 
> defmethod and got a stack overflow (16000).
> 
> Is the recursive defmethod so much more expensive or is it more likely 
> that it is some sort of user (me) error?

It seems to me that CLOS implementations typically don't support tail 
recursion elimination. Maybe that's your problem here. (But that's just 
a guess.)


Pascal

-- 
My website: http://p-cos.net
Closer to MOP & ContextL:
http://common-lisp.net/project/closer/

From: verec
Subject: Re: method vs function recursion
Date: Sat, 19 Nov 2005 09:51:38 +0000
Message-ID: <437ef5aa$0$38044$5a6aecb4@news.aaisp.net.uk>

On 2005-11-19 09:21:32 +0000, Pascal Costanza <··@p-cos.net> said:

> (defmethod flood-fill2 ((this game-map) (x integer) (y integer))
>    (when (not (equal "+" (grid-get-at this x y)))
>      (grid-put-at this x y "+")
>      (flood-fill2 this x (1- y))
>      (flood-fill2 this x (1+ y))
>      (flood-fill2 this (1- x) y)
>      (flood-fill2 this (1+ x) y)))
> 
> (defun flood-fill (this x y)
>    (when (not (equal "+" (grid-get-at this x y)))
>      (grid-put-at this x y "+")
>      (flood-fill this x (1- y))
>      (flood-fill this x (1+ y))
>      (flood-fill this (1- x) y)
>      (flood-fill this (1+ x) y)))

[...]

> It seems to me that CLOS implementations typically don't support tail 
> recursion elimination. Maybe that's your problem here. (But that's just 
> a guess.)

Might be but this seems unlikely. Tail-recursion wise, the defun
version is "stacking" 3 calls out of 4, while your hypothesis is
that the defmethod stacks 0 out of 4. Yes, that's a difference,
but only insofar as a per recursion level 33% increase in stack
consuption is significant, which might, or might not, be the case.
-- 
JFB  ()