Anzeige

Hailstone-Sequenz (Rekursion)


#1
Hallo,

hab folgendes Programm, welches die Hailstone-Sequenz ausgibt:

C:
#include <stdio.h>
#include <stdlib.h>

int hailstone (int n)
{
    return n % 2 ? 3 * n + 1 : n / 2;
}

int main()
{
    int start = 0;
    printf("Geben Sie Ihren Startwert ein: \n");
    scanf("%d", &start);
    
    while (start > 1)
    {
        start = hailstone(start);
        printf("%d\n", start);
    }

return EXIT_SUCCESS;

}
Das Programm an sich funktioniert, nur sollte ich die Funktion mit Rekursion implementieren.

Grundsätzlich weiß ich, was eine Rekursion ist (Funktion, die sich selber immer wieder aufruft, bis eine Abbruchbedingung das Ganze abbricht).
Da ich aber noch nie etwas mit Rekursion gemacht habe, habe ich keine Ahnung, wie ich das bei diesem Programm implementieren kann...

Hat jemand einen Tipp/Hilfestellung?

Viele Grüße
 

cwriter

Erfahrenes Mitglied
#2
Grundsätzlich weiß ich, was eine Rekursion ist (Funktion, die sich selber immer wieder aufruft, bis eine Abbruchbedingung das Ganze abbricht).
Ok, machen wir ein einfaches Beispiel.

C:
for(int i = 0; i < 100; ++i)
    printf("i ist %d\n", i);
Wir haben den Startwert 0, den Endwert 99, und Einerschritte. In jeder Iteration wird etwas ausgegeben. Wir können das also verallgemeinern:

C:
void func(int i)
{
    printf("i ist %d\n", i);
}
void f()
{
    for(int i = 0; i < 100; ++i)
        func(i);
}
Nun können wir wie in der Induktion arbeiten (Die Eigenschaften der Rekursion sind daher für die Theoretische Informatik relativ wichtig (auch Funktionelle Programmierung).
C:
void iter(int i)
{
     func(i);
}
Für iter(0) bekommen wir "i ist 0" heraus - perfekt. Wie bekommen wir jetzt die nächsten Elemente? Ganz einfach: Wir nehmen an, dass wir immer den Vorgängerwert schon haben. Nennen wir den mal k. Für k = 0 haben wir bewiesen, dass es stimmt (einfach durch Ausprobieren). Also können wir weitermachen mit i = k + 1:

C:
void iter(int i)
{
     func(i);
     iter(i + 1);
}
Das geht eine Weile ganz gut, es werden immer grössere i ausgegeben, bis das Programm abstürzt. Das ist ein Problem des Call Stack: Stackoverflow oder Segfault sind die Fehlerbeschreibungen.
Es ist klar: Die Abbruchbedingung fehlt. Also platzieren wir die:
C:
void iter(int i)
{
     if(i >= 100) return;
     func(i);
     iter(i + 1);
}
Wir wollen ja bei 100 nicht mehr weitermachen (oder anders herum: Wir wollen nur bis und mit 99 weitermachen).
Warum die Bedingung nicht nach iter(i+1) platziert werden kann, überlasse ich mal dir :)

Und wenn wir das jetzt wieder zusammenbauen, bekommen wir:
C:
void iter(int i)
{
     if(i >= 100) return;
     printf("i ist %d\n", i);
     iter(i + 1);
}

// Aufruf: iter(0)
Das ist übrigens eine spezielle Rekursion: Sogenannt "Tail-Call Recursion". Diese Art der Rekursion ist sehr angenehm, denn man kann sie sehr leicht wieder in einen Loop verwandeln - was Compiler in der Regel auch tun, da Iterationen auf heutigen Maschinen immer schneller sind als Rekursionen.

Falls es dir hilft: Dein Programm lässt sich so schreiben:
C:
for(int start = startwert; start > 1; start = hailstone(start))
{
    printf("%d\n", start);
}
Alles klar?

Gruss
cwriter
 
Anzeige