From: Juergen Katins <juergen.katins@...>
Date: 2002-07-09T00:04:19+09:00
Subject: Re: Right recursive


"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