Hi!
I know, that recursive functions fill the stack.
I learnt about right recursiveness.
Eg. the fib function:
fib0 n, acc
if n>0
fib0 n-1, n*acc
else
acc
end
end
def fib n
fib0 n, 1
end
The main advantage of the right recursion, that after the fib0 call,
there is nothing, so no need for stack space.
But this is just theory.
The right-recursive version stops execution because of stack overflow.
Will ruby detect this case and support right-recursion?
Gergo
±[Kontra, Gergely @ Budapest University of Technology and Economics]-+
Email: kgergely@mcl.hu, kgergely@turul.eet.bme.hu |
URL: turul.eet.bme.hu/~kgergely Mobile: (+36 20) 356 9656 |
±------“Olyan langesz vagyok, hogy poroltoval kellene jarnom!”-------+
.
Magyar php mirror es magyar php dokumentacio: http://hu.php.net
Hi,
The right-recursive version stops execution because of stack overflow.
It is oftern called “tail recursion”.
Will ruby detect this case and support right-recursion?
My toy prototype bytecode engine does. So will Rite (I hope).
matz.
···
In message “Right recursive” on 02/07/08, “Kontra, Gergely” kgergely@mlabdial.hit.bme.hu writes:
“Kontra, Gergely” wrote
I learnt about right recursiveness.
Eg. the fib function:
fib0 n, acc
if n>0
fib0 n-1, n*acc
else
acc
end
end
def fib n
fib0 n, 1
end
I don’t know the correct formula for right recursion of fibunacci numbers,
but this one is
false (fib 7 should be 13, not 720).
I know, that recursive functions fill the stack.
This is often falsly assumed. Take the example of the intuitive fibonacci
function:
def fib n
if n>2
fib(n-1) + fib(n-2)
else
1
end
end
If you run fib(20) you get some 2^20 calls of fib. But there always only 20
functions existing at the same time and using stack space. The problem with
these recursive calls is not space but time.
The right-recursive version stops execution because of stack overflow.
Must be a problem of acc becoming to big, not the stack usage of the
function fib1.
greetings
Juergen
The given function calculate n! not the fibonacci numbers.
-billy.
···
On Tue, Jul 09, 2002 at 12:04:19AM +0900, Juergen Katins wrote:
“Kontra, Gergely” wrote
I learnt about right recursiveness.
Eg. the fib function:
fib0 n, acc
if n>0
fib0 n-1, n*acc
else
acc
end
end
def fib n
fib0 n, 1
end
I don’t know the correct formula for right recursion of fibunacci numbers,
but this one is
false (fib 7 should be 13, not 720).
–
Meisterbohne Söflinger Straße 100 Tel: +49-731-399 499-0
eLösungen 89077 Ulm Fax: +49-731-399 499-9