Rekursion

Erhard Henkes

warum beginnt die Funktion rekursion bei der Ausgabe mit 1 und nicht bei 10?

#include <iostream>
using namespace std;

void rekursion( int n )
{
    if( n>1 )
    {
      rekursion( n-1 ); // hier ruft sich die Funktion selbst auf! 
    }
    cout << "Rekursion: " << n << endl;
}

int main()
{
    for( int i=0; i<10; ++i )
    {
      cout << "Iteration: " << i+1 << endl;
    }

    cout << endl;

    rekursion(10);
}

Wie weit kann man es mit dieser Endlosschleife treiben? Wovon hängt das ab?

#include <iostream>
#include <conio.h>
using namespace std;

int i;

void sageHallo()
{   
    ++i;
    cout << "hallo " << i << " "; 
    if(i<120000) sageHallo(); // Rekursion ! Wie hoch kann man i treiben?
}    

int main()
{
    sageHallo();
    getch();
}

Taurin

void rekursion( int n )
{
    if( n>1 )
    {
      rekursion( n-1 ); // hier ruft sich die Funktion selbst auf!
    }
    cout << "Rekursion: " << n << endl;
} 

Aufruf: rekursion(10)

Das erstemal, dass sich die Rekursion nicht selbst aufruft, tritt bei dem Fall,
n == 1 auf. Daraufhin folgt die Ausgabe und die Rekursion springt zum nächsten
Aufruf zurück.

Edit: ach ja, da gibts ja noch Teil zwei:

int i;

void sageHallo()
{  
    ++i;
    cout << "hallo " << i << " ";
    if(i<120000) sageHallo(); // Rekursion ! Wie hoch kann man i treiben?
}

Bei jedem selbstaufruf einer Funktion werden auf dem Stack lokale Variabelen
(gibts hier nicht) und vor allem die Rücksprungsdresse für den Rücksprung in die
nächst höhere Stufe der Rekursion gelegt. Und irgendwann ist der Stack nu mal voll.

DrGreenthumb

warum beginnt die Funktion rekursion bei der Ausgabe mit 1 und nicht bei 10?

Naja, der letzte Wert den i annimmt bevor die if-Bedingung false wird, ist 1.

Wie weit kann man es mit dieser Endlosschleife treiben? Wovon hängt das ab?

hm, irgendwann ist der Stack voll. Wenn du es ohne Ausgabe probierst, geht das ziemlich schnell.
Den Wert von i kann man sich im Debugger angucken:

Program received signal SIGSEGV, Segmentation fault.
0x080485c1 in rekursion(int) (n=698907) at a.cc:6
6           rekursion(n + 1);

Das erste Beispiel ist verwirrend. Wie klappt das mit dem Zurückspringen genau, sodass von 1 bis 10 gezählt wird?

Wovon hängt die Zahl bei beispiel 2 ab? Vom OS?

Wenn man "cout << "Rekursion: " << n << endl;" vor den if-Zweig setzt, zählt die Funktion von 10 bis 1.

Vellas

Hi!

@Erhard Henkes:
Stimmt, vwxyz hat recht. Das Thema hatte ich letztens beantwortet, vielleicht magst du mal reinsehen, da habe ich sowas beschrieben, für das umdrehen eines Strings:
http://www.mycsharp.de/wbb2/thread.php?threadid=2044
Das Problem vom Threadstarter entspricht deiner Rekursion.

Code-Hacker

Erhard Henkes

Danke für die Antworten. Kann man die Größe des Stacks aus dem Programm heraus verändern? Gibt es einen guten Link zu diesem Thema "Stack" eines Programms, das auf dieses Thema darauf eingeht?

Für die Leser dieses Themas hier noch ein Beispiel, das den vorteilhaften Einsatz von Rekursion gegenüber Iteration demonstriert:

#include <iostream>
#include <conio.h>

unsigned factorial_rekursiv(unsigned zahl)
{
  if( !zahl )
      return 1;
  else
      return zahl * factorial_rekursiv( zahl - 1 );
};

unsigned factorial_iterativ(unsigned zahl)
{
  if( !zahl )
      return 1;
  else
  {
      int fakultaet = 1;
      do
      {
        fakultaet *= zahl;
      } while ( --zahl > 1);
      return fakultaet;
  }
}

int main()
{
  unsigned value;
  std::cout << "Zahl eingeben: ";
  std::cin >> value;
  std::cout << "Fakultaet (rekursiv): " << factorial_rekursiv(value) << std::endl; 
  std::cout << "Fakultaet (iterativ): " << factorial_iterativ(value) << std::endl;   
  getch();
}

Hi Erhard Henkes,

welchen Vorteil willst du uns mit deinem Beispiel eigentlich demonstrieren.
Rekursive Lösungen sind meist recht elegant, aber nur selten so effizient wie iterative Lösungen.

Falls du die textuelle Kürze der rekursiven Lösung hervorheben wolltest, es geht auch deutlich kürzer (und dennoch lesbar), als bei dir.

unsigned factorial_iterativ(unsigned zahl) 
{ 
  unsigned fakultaet = 1; 
  for (long i = zahl; i > 1; --i)
    fakultaet *= i;
  return fakultaet;
}

groovemaster

Erhard Henkes schrieb:

Kann man die Größe des Stacks aus dem Programm heraus verändern?

Nein.

Also für MSVC 6.0 kann man die Stackgrösse für das Programm durchaus ändern. Dazu dient der Compiler-Schalter /F.

John Doe

Ich glaube die Frage war ob die Änderung zur Laufzeit möglich ist. Der Compiler-Schalter /F hat jedoch nichts mit Änderungen der Stack-Grösse zur Laufzeit zu tun.

mfg JJ