functional programming & tail recursion?

[Hannah Schroeter]

Hello!

In article <NDBBKEGCHLLCCFMJKMIHKEGPDAAA.infonuovo at email.com>,
Dennis E. Hamilton <infonuovo at email.com> wrote:
>I'm curious,

>I can't imagine any language providing a very good result for

>	def fib(n):
>          assert n = int(n) and n = abs(n)
>          if n in [0, 1]:
>              return n
>          return fib(n-1) + fib(n-2)

>or any descriptive-language equivalent (Eiffel?).

You must differentiate between languages and language implementations.

For purely functional languages, there's a technique, described
e.g. in the book on functional programming by Field and Harrison,
which CAN convert the definition
  fib n | n < 0 = error "foobar"
        | n < 2 = n
        | otherwise = fib (n-1) + fib (n-2)

into something like
  fib n | n < 0 = error "foobar"
        | n < 2 = n
        | otherwise = fib_h 1 1 2
    where
      fib_h a1 a2 i | i == n = a2
                    | otherwise = fib_h a2 (a1+a2) (i+1)

(in a Haskell notation)

However, I haven't seen that implemented in any real world
implementation yet.

>[...]

Regards, Hannah.