{ File: fibonacc.pas }

{ Scopo: esempio di funzione ricorsiva con ricorsione multipla }

program CalcoloFibonacci;
{ Dato un numero intero n calcola l'n-esimo numero di Fibonacci usando una
  funzione iterativa o ricorsiva.

  L'i-esimo numero di Fibonacci F(i) e` definito attraverso la seguente
  definizione induttiva:

     F(i) = 0                 se i = 0
     F(i) = 1                 se i = 1
     F(i) = F(i-1) + F(i-2)   se i >= 2
}

{ Utilizza il tipo predefinito del TurboPascal longint, che permette di
  rappresentare interi nell'intervallo da -2^31 a 2^31-1. }

var
  numero : longint;


  function Fibonacci (n: longint): longint;
  { Calcola l'n-esimo numero di Fibonacci usando un metodo ricorsivo. }
  begin
    if n = 0 then
      Fibonacci := 0
    else if n = 1 then
      Fibonacci := 1
    else
      Fibonacci := Fibonacci(n - 1) + Fibonacci(n - 2)
  end; { Fibonacci }


  function FibonacciIterativa (n: longint): longint;
  { Calcola l'n-esimo numero di Fibonacci usando un metodo iterativo. }
  var
    a, b, f : longint;
    i       : integer;
  begin
    if n = 0 then
      FibonacciIterativa := 0
    else
    begin
      b := 0;
      f := 1;
      for i := 1 to n-1 do
      begin
        a := b;
        b := f;
        f := a + b
      end;
      FibonacciIterativa := f
    end
  end; { FibonacciIterativa }


begin { CalcoloFibonacci }
  numero := 0;
  repeat
    write('Immetti un numero intero nonnegativo (o negativo per terminare)! ');
    readln(numero);
    if numero >= 0 then
      writeln('Il ', numero, '-simo numero di Fibonacci e'': ',
              Fibonacci(numero)
            { FibonacciIterativa(numero) }
              )
  until numero < 0
end. { CalcoloFibonacci }