Fibonacci-Algorithmus als tail-rekursive Funktion implementieren

SirLant

Ne einfache Implementierung wäre das hier:

int fibonacci(int n) {
	if (n<=1) return n;
	else return fibonacci(n-1)+fibonacci(n-2);
}

Ist es möglich dies tail-rekursiv zu implementieren? Ich hab das bisher nur mit
Funktionen gemacht, die sich 1mal und nicht 2mal aufrufen.
Ist das hier möglich?

volkard

kannst du sowas machen?
pair<int,int> fibonacci_impl(pair<int,int>);
damit müßte es klappen, die beiden zahlen so durchhuschen zu lassen, als wäre es eine schleife.

3rr0r

hi.
möchteste einfach mal mein fib. code haben?
glaub ich zwar net, aber egal, dann steht er zumindest mal hier imforum

#include <stdio.h>
#include <stdlib.h>
/* Umlaute in der Konsolenausgabe */
#include "umlaute.h"

#define  MAXZEILEN 32
#define  MAXZAHL   83

int main ()
{
   int     i, zahl;
   double  fib1 = 1, fib2 = 1, fib;
   int     zeilen = 0;

   /* Obergrenze einlesen */
   do
   {
      printf ("Geben Sie eine Obergrenze (max. %d) f%cr die Ermittlung von Fibonaccizahlen ein: ",
               MAXZAHL, ue );
      scanf ("%d", &zahl);
   } while ( zahl < 0 || zahl > MAXZAHL );

   printf ( "Die Fibonaccizahlen sind:\n" );
   /* Schleife über alle gewünschten Fibonaccizahlen */
	for (i = 1; i <= zahl; i++)
	{
	   if ( i == 1 || i == 2 )
         fib = 1;
	   else
      {
         /* Addition der letzen beiden Zahlen */
         fib = fib1 + fib2;
         /* die beiden letzten Zahlen merken für Addition im nächsten Schritt */
         fib1 = fib2;
         fib2 = fib;
      }
      /* Ausgabe */
      printf ( "% 3d.\t%.0lf\n", i, fib );
      zeilen++;

      /* Zeilenzähler überwachen */
      if ( zeilen == MAXZEILEN )
      {
         system ("pause");
         zeilen = 0;
      }
   }
   system ("pause");
}

mfg
err0r

neverbeenhere

3rr0r schrieb:

hi.
möchteste einfach mal mein fib. code haben?
glaub ich zwar net, aber egal, dann steht er zumindest mal hier imforum

wenn er code haben wollte, dann wohl bestimmt keine iterative lösung der titel hieß schließlich

Fibonacci-Algorithmus als tail-rekursive Funktion implementieren

:p aber egal *g*

SirLant

Das ist eine Iterative Lösung, ist natürlich schneller, aber mir ging es um die
Implementation mit Hilfe einer Tail-Rekursion.

Volkard, wie könnt ich das denn implementieren? Benötige, dort doch auch für jede einen Aufruf

volkard

SirLant schrieb:

Volkard, wie könnt ich das denn implementieren? Benötige, dort doch auch für jede einen Aufruf

du kriegt durch einen aufruf gleich die beiden letzten zahlen!

Hallo,

nach C gepfuscht aus "The Scheme Programming Language":

int fib(int i, int a1, int a2) {
    if(i == 1)
        return a1;
    else
        return fib(i-1, a1+a2, a1);
}

int fibonacci(int a) {
    if(a == 0) 
        return 0;
    else
        return fib(a, 1, 0);
}

Gruß

SirLant

Danke, habs aber inzwischen schon selber hinbekommen, auch wenn ich das pair weglassen
könnte wie in deiner Methode

int fib (pair<int, int> n, int a) {
	if (a <= 1)
		return n.first;
	return fib (pair<int, int> (n.first + n.second, n.first), a-1);
}
int fibonacci(int n) {
	return fib (pair<int, int> (1, 0), n);
}

Edit:
Typo

volkard

ich auch.

pair<int,int> fib_impl(pair<int,int> old,int n)
{
	if(n==1)
		return old;
	else
		return fib_impl(make_pair(old.second,old.first+old.second),n-1);
}

int fib(int n)
{
	return fib_impl(make_pair(0,1),n).second;
}

eures ist wohl hübscher.

Bashar

SirLant schrieb:

Das ist eine Iterative Lösung, ist natürlich schneller, aber mir ging es um die
Implementation mit Hilfe einer Tail-Rekursion.

Witz komm raus!
Iteration und Endrekursion sind im Prinzip das gleiche, das ist ja gerade der Grund, warum Endrekursion diesen besonderen Status hat. Sie lassen sich fast(?) mechanisch ineinander überführen.

SirLant

Bashar schrieb:

SirLant schrieb:

Das ist eine Iterative Lösung, ist natürlich schneller, aber mir ging es um die
Implementation mit Hilfe einer Tail-Rekursion.

Witz komm raus!
Iteration und Endrekursion sind im Prinzip das gleiche, das ist ja gerade der Grund, warum Endrekursion diesen besonderen Status hat. Sie lassen sich fast(?) mechanisch ineinander überführen.

Die Funktionsaufrufe hat man immernoch, wenn man es, aber als eine Schleife die
über eine Rekursion implementiert wurde (so wie es in funktionalen Sprachen ja der Fall ist),
dann hast du natürlich recht.