|
|
|
|
Subject: Re: function recursive
From: Pierre Bommel (bommel@cirad.fr)
Date: Mon Nov 24 2003 - 11:23:26 CET
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
>
>
> 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/~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 ***********************************