|
|
|
|
Subject: Re: function recursive
From: Christophe Le Page (christophe.le_page@cirad.fr)
Date: Sat Nov 22 2003 - 04:08:09 CET
Hello Diana,
Yes , it is possible, but be very careful about never-ending "ping pong"
call of the function ! In your case for instance, this will happen if
two neighbouring cells have water !!!
Recursivity is elegant but somehow this elegance has a cost when
recursivity is heavily used : it is time-consuming because of the
repetition of message sending (activation/return delay). A good
illustration of that is the factorial calculation. In VW, it is not
implemented in a recursively way (look below Integer>>factorial)
factorial
"Answer the factorial of the receiver. Fail if the
receiver is less than 0.
For example, 6 factorial == 6*5*4*3*2*1."
| tmp |
self < 0
ifTrue: [^self class
raise: #domainErrorSignal
receiver: self
selector: #factorial
errorString: (#errFactorialInvalid << #dialogs >> 'Factorial
is invalid on negative numbers')].
tmp := 1.
2 to: self do: [:i | tmp := tmp * i].
^tmp
Just for the sake of this test, I've written a recursive version at the
Cormas class level (look below Cormas>>factorial:)
factorial: n
n < 0 ifTrue: [^nil].
n = 0 ifTrue: [^1].
^n * (Cormas factorial: n - 1)
Then I've performed some tests to compare the both implementations (see
below the benchmarking code that I've run from the VisualWork Transcript)
| tot1 tot2 x |
x := 30.
0 to: 5000 by: 50 do:
[:n |
tot1 := 0.
tot2 := 0.
x timesRepeat:
[tot1 := tot1 + (Time microsecondsToRun:
[CormasNS.Kernel.Cormas factorial: n])].
x timesRepeat:
[tot2 := tot2 + (Time microsecondsToRun: [n factorial])].
Transcript cr.
n printOn: Transcript.
Transcript tab.
(tot1 / x) asFloat printOn: Transcript.
Transcript tab.
(tot2 / x) asFloat printOn: Transcript.
Transcript flush]
If you select this code and run it, you get directly the data in the
transcript. As you can see, the non-recursive function is definitively
faster.
clp
-- Christophe Le Page CIRAD - TERA TA 60/15 - 34398 Montpellier Cedex 5 - France Tél: +33 467 593 832 Fax: +33 467 593 827 http://cormas.cirad.frDiana Adamatti a écrit:
> Hello! > > My doubt is about SmallTalk. I'd like to call a function recursive. Is > it possible? > > > For example: > > functionA: cell > neighbourhood := cell recursiveNeighbourhood: 1. > neighbourhood do: > [:a | (a occupantAt: #Water) size > 0 > ifTrue: > [self functionA: a.]]. > > Where I call functionA inside its definition. > > Thank you. > > Diana Adamatti > Laboratório de Técnicas Inteligentes - LTI > Escola Politecnica da Universidade de Sao Paulo - USP > http://www.lti.pcs.usp.br/~adamatti > <http://www.lti.pcs.usp.br/%7Eadamatti>