|
|
|
|
Subject: Re: function recursive
From: ABRAMI Géraldine (Geraldine.Abrami@montpellier.cemagref.fr)
Date: Mon Nov 24 2003 - 12:00:47 CET
I bring my little interrogative stone to the debate.
How is it possible to transform a recursive call into an iteration when
the recursion covers forks?
Ok I try to explain :
In my model of water management, I model water circulation with a
flow propagating via nodes and branches with a recursive fonction which
is basically :
propagateDownFlow: aFlow
self flow: aFlow.
"branchesOut are the branches I distribute water to"
self branchesOut do: [:b | |flowB|
flowB := self flowFor: b. "computes the
flow that will be given to b"
self propagateDownFlow: flowB].
and the recursion stops when branchesOut is empty, i.e. when the end of the
embranchment is reached.
I've tried to wonder how to transform this into an iteration (it is
actually going quite slow!) with a while loop or something but I can't see
how it is possible to get along with the forks, whithout knowing by advance
how many of them will occur or how long the embranchments will be...
Geraldine
At 11:23 24/11/2003 +0100, vous avez écrit:
>Wahoooo, what an answer !!!
>Congratulation CLP and thank's for the benchmarks !
>Just some more few words to Diana :
>Recursion is a way of specifying a process by means of itself.
>In order not to get into an never-ending loop, you should keep in mind a
>rule to write recursive functions :
>You always need a test (at least one) and 2 ways to leave the method (2
>returns).
>The test : every recursive method must check for the "base case" (or the
>stopping case, or the trivial case or pre-conditions) before the recursion
>is done. The test is done when an input value gives a trivial result, it
>is returned directly.
>Otherwise the function calls itself, passing a changed version of the
>input values. This second call should return a value.
>factorial example :
>
>factorial: n
> "Base Case Tests"
> n < 0 ifTrue: [^nil].
> n = 0 ifTrue: [^1].
> "Recursion step"
> ^n * (Cormas factorial: n - 1)
>
>When the argument reaches 0, the exit condition is satisfied, and the
>recursion stops.
>Otherwise, a recursive call is made to factorial(n-1), the returned value
>is multiplied
>by n, and the result returned.
>A stack is a last-in, first-out storage structure. As Christophe said, the
>Stack consumes system resources:
> 1. factorial 3
> 2. 3 * factorial 2
> 3. 3 * 2 * factorial 1
> 4. 3 * 2 * 1 * factorial 0
> 5. 3 * 2 * 1 * 1
> 6. 3 * 2 * 1
> 7. 3 * 2
> 8. 6
>You can notice that the size of the expression first grows, then shrinks
>as the pending multiplications are completed.
>
>Here is another recursive function called power (equivalent to raisedTo:
>method in VW) :
>power: n "equivalent to raisedTo: n method in VW"
> "Base Case Test"
> n = 0 ifTrue: [^1]. " X power: 0 returns 1 even if X = 0"
> "Recursion step"
> ^self * self power: (n - 1)
>
>ex:
> 4 power: 3 =
>=> 4 x (4 power: 2) =
>=> 4 x (4 x (4 power: 1)) =
>=> 4 x (4 x (4 x (4 power: 0))) =
>=> 4 x (4 x (4 x 1)) = 64
>
>Any method that includes a recursive call can be re-written to use
>iteration rather than recursion. The methods rewritten without recursion
>typically have loops. Iterative methods generally run faster and use less
>memory space. So when should you use recursion?
>when efficiency is not important and it makes the code easier to understand.
>
> Pierre
>
>Christophe Le Page a écrit :
>>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.fr>http://cormas.cirad.fr Diana Adamatti a écrit:
>>>Hello!My doubt is about SmallTalk. I'd like to call a function
>>>recursive. Is it possible? For example:functionA: cellneighbourhood :=
>>>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/%7Eadamatti>http://www.lti.pcs.usp.br/~adamatti
>--
>***********************************
> Pierre Bommel
> CIRAD TA 60/15
> 73, rue Jean-François Breton
> 34398 Montpellier cedex 5 France
> Phone: +33 (0)4 67 59 38 53
> Fax: +33 (0)4 67 59 38 27
> <http://cormas.cirad.fr>http://cormas.cirad.fr
>***********************************
>
----------
Géraldine Abrami
Doctorante
CEMAGREF-IRMO
361, rue J.F. Breton
B.P. 5095
34033 MONTPELLIER Cedex 1
tel : +33 (0)4 67 04 63 54
email : abrami@montpellier.cemagref.fr