Jag testade en version av Fibonacci som ser ut på följande sätt:

int fibonacci(int Tal) {
	int FibTal;

	FibTal = Tal;

	if (Tal == 0 || Tal == 1 ) 
		return Tal;
	else
		for(int i = 1;i == Tal;i++)
			FibTal = FibTal + i;

	return FibTal;
}

Problemet är att den inte plusar på i på FibTalet.

Dvs om Tal är 3 blir FibTal också 3.

Någon som har nån fundering?

Det är knappast kompilatorn som har gjort fel. Till att börja med är det ett mycket ovanligt sätt att skriva Fibonacci-funktionen på, och fel på minst två sätt.

Bestäm dig först för om du vill köra med
1. en rekursiv variant
2. dynamisk programmering
3. en iterativ variant

Felen är:
1. for-satsen har ett == där det skall vara någon av !=, < eller <=.
2. Du kommer få "ackumulerade summan", snarare än Fibonaccitalet.

det fungerade med att ändra == till < tack

Alternativt så kan man ju initiera FibTal till 0 i stället för till Tal, känns enklare att förstå vad som händer då. Se i övrigt Niklas kommentarer, framförallt hur fibonacci egentligen definieras:

F(n) = F(n-1) + F(n-2)
F(0) = 0
F(1) = 1

Den rekursiva varianten,

int F(int n)
{
    if (n == 0)
        return 0;

    if (n == 1)
        return 1;

    return F(n-1) + F(n-2);
}

är väldigt ineffektiv.

Betydligt effektivare är en enkel iterativ variant:

int F(int n)
{
    int x0 = 0, x1 = 1;
    int i;

    for (i=0; i<n; i++) {
        int x2 = x0 + x1;
        x0 = x1;
        x1 = x2;
    }

    return x0;
}

För stora n finns det en variant som är ännu effektivare. Den bygger på att den iterativa varianten egentligen utför vektor- och matrisberäkningen z = A^n z0, där z=(x0, x1), z0=(0, 1) och A=((0, 1), (1, 1)), samt att "upphöjt till" kan beräknas effektivt genom A^(2n) = (A^n)^2. Det blir mer avancerade beräkningar, så för små n lönar sig inte algoritmen.

Kuriosa, appropå ingenting.
De flesta kompilatorer optimerar ändå den rekursiva lösningan till en WHILE loop.

//Håkan

Håkan... Jag tror du har fel. Enkelt rekursiva funktioner går bra att optimera till en iteration, men inte dubbelt rekursiva.

Om du tror annorlunda, visa gärna hur koden skrivs om. Visa eventuellt assembly.

Tail-recursive går ju alltid att fixa, men går verkligen alla enkla anrop?
Vad blir då nånting i stil med följande?

int a(int n)
{
if(n==0)
return 0;
b;
c=a(n-1);
d;
return f(c, d);
}


Sen skulle ju en kompilator teoretiskt sett kunnna fixa en dubbel rekursion, om bara två koder är ekvivalenta...

EDIT: vad fan skriver jag...?
ändrade koden lite.

Per och Niklas.

Syftar på en "enkel" rekursion enligt Pers exempel ovan, inget annat.

//Håkan

Men rekursionen ovan är inte enkel; du gör två anrop till funktionen. Hur menar du att man skulle kunna optimera bort det?

(Naturligtvis går det ju teoretiskt sett, men i praktiken?)

Går det ens teoretiskt utan att införa en egen stack?

<b>Niklas:</b> Nä precis (inte enkel) fort (läst) och fel (svar) blev det.
Så för klarhets skull så menar jag tail (enkel) rekursion.

<b>Per:</b> Tror du att en stack är den datastruktur som skulle kunna göra jobbet?
En trädstruktur (av något slag) känns mer rätt (OBS, spekulerar).
Men det ligger utanför mitt område, och du/ni har nog mer koll.
Läste inte läste kursen Compiler Construction (hade varit mycket intressant).

//Håkan

>Tror du att en stack är den datastruktur som skulle kunna göra jobbet?

Svansrekursionen är som sagts tidigare enkel att göra om till iteration men den första rekursionen behöver spara tillståndet och då behövs det en stack.

Quicksort fungerar på samma sätt med dubbel rekursion och där brukar man använda en stack.

<b>>Går det ens teoretiskt utan att införa en egen stack?</b>
Med teoretiskt menar jag följande (obs, <b>mycket</b> teoretiskt =) ):

Vi har en funktion A som inte har några bieffekter utan för varje input x genererat ett specifikt output y.
Om vi nu kan konstruera en funktion B som inte heller har några sideffekter, och ändå genererar samma grejer (A(x)=B(x) för alla x), så är de ju ekvivalenta.

En "tillräckligt smart kompilator" (vilket sannolikt är mer eller mindre omöjligt) skulle ju därför kunna översätta A till B. A är den rekursiva och B är den iterativa.


Problemet här är ju stackstorlek, etc., och att dessa då i princip genererar sidoeffekter, men om vi tänker oss oändligt minne och oändligt stora int:ar, så...

(Jag inser naturligtvis att detta aldrig kommer att funka i praktiken, tro inget annat.)

Okej, men då handlar det om olika algoritmer. När man talar om att svansrekursion kan överföras i iteration handlar det i princip om samma algoritm, bara olika sätt att skriva den.


<b>Tror du att en stack är den datastruktur som skulle kunna göra jobbet?
En trädstruktur (av något slag) känns mer rätt (OBS, spekulerar).</b>

Jag förstår varför du tycker att en trädstruktur känns mer rätt, men kan inte se hur en sådan skulle kunna användas. Hur går man genom ett träd utan att använda rekursion?

En stack används varje gång en funktion anropas, t.ex. vid rekursion. För att få en iterativ kod kan man manuellt implementera det som kompilatorn och processorn utför vid rekursiva anrop, eller använda stacken på andra sätt, t.ex. för att lagra delresultat.

<b>>Okej, men då handlar det om olika algoritmer. När man talar om att svansrekursion kan överföras i iteration handlar det i princip om samma algoritm, bara olika sätt att skriva den. </b>
Tja, det är ju en definitionsfråga. Om man tänker på något så enkelt som fakulteten, så utgår man ju från två (naturligtvis ekvivalenta) ekvationer; ena implementerar man iterativt, andra som rekursivt:

x(n)=n*(n-1)...

resp.

x(0) = 1
x(n) = n*x(n-1)

Visst, naturligtvis känns det som att det är i stort sett samma algoritm, men det är ju en gradfråga. Om två funktioner ger samma svar så är defintionerna ekvivalenta, och då är det ju i någon mening ekvivalenta algoritmer. Var går gränsen mellan ekvivalent och "samma" algoritm?

En lämplig definition av "samma algoritm" är att den ena kan överföras i den andra genom en serie enkla transformationer (där förstås mängden av tillåtna sådana transformationer måste definieras). Svansrekursion kan enkelt överföras i iteration, men att överföra F(n) = F(n-2) + F(n-1) till en iteration är jag tveksam till att det skulle gå.

Ovanstående ger vad jag vill kalla "ekvivalens av algoritmer". Att två algoritmer ger samma svar innebär bara att de implementerar samma funktion. Det är förvisso också en ekvivalensrelation, men inte av sådan art att jag vill säga att de utgör "samma" algoritm.

Jag anser att p0(n)=2*2*...*2 (n st) och p1(0) = 1, p1(n) = 2*p1(n-1) utgör samma algoritm, medan p2(0) = 1, p2(2n) = (p2(n))^2, p2(2n+1) = 2*p2(2n) utgör en annan algoritm. Alla tre implementerar dock samma funktion, 2^n (för n=0, 1, ...).

Nu är vi visserligen inne på för frågeställningen löjligt teoretiska utläggningar, men;

<b>>(där förstås mängden av tillåtna sådana transformationer måste definieras)</b>
Och där är pudelns kärna. Det är alltså bara en gradfråga; vad är en "enkel transformation", var går gränsen mellan "samma" och "likadana".

För även om de är "samma" algoritm så är ju inte beskrivningarna av dem identiska, då hade vi inte sagt att det var två olika algoritmer (p0, p1) från början.

Det kan ju dras ner på väldigt mycket enklare nivå;
är 1+1 och 2 samma sak?
är 2+2 och 4 samma sak?
är 2*2 och 4 samma sak?
är 2^2 och 4 samma sak?
är 2^2 och (1+1)*2 samma?

Definitionsfråga, helt enkelt.

Självklart är det en definitionsfråga. Men de kriterier man skall ha när man väljer de tillåtna transformationerna är att de skall vara
1) uppenbara (enkelt att förstå och acceptera att de inte förändrar vad en algoritm implementerar),
2) generella (inte specifika för en liten mängd algoritmer),
3) å andra sidan inte för generella (att säga att två algoritmer får överföras i varandra om de implementerar samma funktion går fetbort).

Borde inte en Tail-recursive funktion se ut

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

int fib(int a, int c, int d)
{
    if (a <= 1)
        return d

    return fib(a - 1, d, c + d)
}

Intressant diskussion, hoppas inte jag avbryter den alltför mycket då jag av en händelse sitter jag med Mathschallenge.net och lurar på ett Fibonacci-problem och har där med viss framgång använt matris-metoden (som omnämndes ovan) så jag publicerar min kod här utifall att den gör någon nytta för någon. Koden använder sig av klassen BigInteger som finns hos The CodeProject (http://www.codeproject.com/csharp/BigInteger.asp) eftersom jag just nu söker efter ett specifikt Fibonaccital F(k) där k ligger runt 500 000, vilket resulterar i ett tal som är ca 120 000 siffror långt.

Tar gärna emot förslag på hur denna kan optimeras för det tar någon minut att räkna ut ett enda Fibonaccinummer just nu och jag har ingen aning om hur långt upp jag måste leta...

        private BigInteger Fibonacci(long n)
        {
            if (n < 2) return new BigInteger(n);
            BigInteger[,] matrix = new BigInteger[2, 2] { { new BigInteger(1), new BigInteger(1) }, { new BigInteger(1), new BigInteger(0) } };
            return PowerMatrix(matrix, n - 1)[0, 0];
        }

        private BigInteger[,] PowerMatrix(BigInteger[,] A, long n)
        {
            if (n == 1) return A;
            if (n % 2 == 0) return PowerMatrix(MultiplyMatrix2By2(A, A), n / 2);
            return MultiplyMatrix2By2(A, PowerMatrix(MultiplyMatrix2By2(A, A), (n - 1) / 2));
        }

        public static BigInteger[,] MultiplyMatrix2By2(BigInteger[,] A, BigInteger[,] B)
        {
            if (A.GetLength(0) != 2 || A.GetLength(1)!=2 || B.GetLength(0)!=2 || B.GetLength(1)!=2) throw new ArgumentException("Wrong dimensions!");

            BigInteger[,] result = new BigInteger[2,2];

            result[0, 0] = A[0, 0] * B[0, 0] + A[0, 1] * B[1, 0];
            result[0, 1] = A[0, 0] * B[0, 1] + A[0, 1] * B[1, 1];

            result[1, 0] = A[1, 0] * B[0, 0] + A[1, 1] * B[1, 0];
            result[1, 1] = A[1, 0] * B[0, 1] + A[1, 1] * B[1, 1];

            return result;
        }

[Edit: Insåg just nu att jag postade C#-kod i ett C++-forum. Sorry!]

Andreas, det räcker med

int fibonacci(int n)
{
    return fib(n, 0, 1);
}

int fib(int a, int c, int d)
{
    if (a == 0)
        return c;

    return fib(a - 1, d, c + d)
}

Genom en enkel transformation kommer man fram till en icke-rekursiv lösning:

int fib(int a, int c, int d)
{
    while (1) {
        if (a == 0)
            return c;

        int a_new = a - 1;
        int c_new = d;
        int d_new = c + d;

        a = a_new;
        c = c_new;
        d = d_new;
    }
}

som sedan kan stoppas in i den övre funktionen för att undvika alla former av anrop:

int fibonacci(int a)
{
    int c = 0;
    int d = 1;

    while (1) {
        if (a == 0)
            return c;

        int a_new = a - 1;
        int c_new = d;
        int d_new = c + d;

        a = a_new;
        c = c_new;
        d = d_new;
    }
}

Låt mig börja med ett citat:
<info>"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil."</info>
- Tony Hoare

Jag har jobbat med Erlang(http://www.erlang.se/) det senaste halvåret. Erlang där det saknas möjlighet att iterera/"loopa". Samtligavariabler är Write once. Man iterera där genom rekusion.

Erlangs styrka är att det väldigt effektivt på concurrency, distrubuerat, osv. Utvecklat av ericsson.

En applikation som intressant är Yaws(http://yaws.hyber.org/) vilket är en webbserver med hög prestanda.

Så jag frågar mig, Vad vinner man på din variant? Är vinsten vär det fler rader kod som resulterar? Kan man inte se varje ytterligare rad kod som en potencielt felkälla?

Min första variant var väl ändå kortare och renare än ditt förslag?

De andra (mer utvecklade eller mer invecklade beroende på tycke) varianterna skrev jag med anledning av diskussionerna angående kompilatorers omskrivning av svansrekursiva funktioner till iteration (loopar). Jag hävdade aldrig att de var bättre.

Ditt första exempel är kort och renare. Men det är inte Tail-recursive. Om man skall skriva rekursiva funktioner bör det helst vara Tail-recursive.

Fördelen med recursiva funktioner är att det ofta ger minder kod än vid iterationer. Ta till exempe sorteringsalgoritmer. Där den rekursiva varianten ofta innebär enklare kod.

Då jag tycker ditt första inlägg gav skenet av att recursivitet är ineffektivt. Ville jag med mitt inlägg poängtera att recursiva funktioner är bra rätt använt. Detta kanske jag gjorde något klumpoigt. Då jag inte är C/C++ kodare eller insatt i Fibonacci problemet.

Skulle inte

int fibonacci(int n)
{
    return fib(n, 0, 1);
}

int fib(int a, int c, int d)
{
    if (a == 0)
        return c;

    return fib(a - 1, d, c + d)
}

vara svansrekursiv?

Jag syftade på ditt första exempel:

<b>Den rekursiva varianten,</b>

int F(int n)
{
    if (n == 0)
        return 0;

    if (n == 1)
        return 1;

    return F(n-1) + F(n-2);
}

<b>
är väldigt ineffektiv.
</b>

Det andra exempel är jag nöjd med. Inget att klaga på.

Ah, okej. Rekursion i sig är inte ineffektivt, men <b>för fibonaccitalen</b> är det mycket ineffektivt att använda den "dubbelt rekursiva" implementationen.