rekursive Methode

angreifer

Hallo,

ich habe zum Wintersemester 09/10 angefangen Regenerative Energietechnik zu studieren und habe somit auch EDV/Informatik und lerne dort C#. Bisher habe ich das alles auch so weit verstanden, doch dann kamen die rekursiven Methoden. Habe auch herausgefunden, wie man die verwendet, doch ihre Funktion verstehe ich nicht ganz. Das hier ist mein Code zur Berechnung der Fakultät, einmal iterativ und einmal rekursiv. Kann mir jemand erklären, was genau bei der rekursiven Methode vorgeht, am besten auch genau an dem Beispiel?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Cosinus {
  class Program {
    static void Main(string[] args) {

      Console.WriteLine("Geben Sie ein n ein, für das die Fakultät berechnet werden soll");
      int n = Convert.ToInt32(Console.ReadLine());  

      double ergebnis = Fakultät_Iter(n);
      double ergebnis2 = Fakultät_Rekur(n);

      Console.WriteLine(Fakultät_Iter(n).ToString());
      Console.WriteLine(Fakultät_Rekur(n).ToString());

      Console.ReadLine();
    }

    static double Fakultät_Iter(int aN){
      if (aN == 0) return 1.0;
      double n = 1;
      double x = n;
      do {
        n = n * x;
        x++;
      } while (x <= aN);
      return n;      
    }

    static double Fakultät_Rekur(int aN) {
      double ergebnis;
      if (aN == 0) 
      {
        return 1.0;
      }
      else{//Rekursive Vereribarung
      ergebnis  = aN*Fakultät_Rekur(aN-1); //Eingegebene Zahl * 
      return ergebnis;
      }

    }
  }
}

Vielen Dank für eure Hilfe!

Jesper

Firefighter

Was genau verstehst du denn nicht?
Eine rekursive Funktion ruft sich selber immer wieder neu auf bis sie durch ein Abbruchkriterium beendet wird.
Das "komplexe" und gefährliche ist, dass man eventuell das Abbruchkriterium falsch implementiert und man somit eine unendliche rekursionstiefe erreicht bis man eine OutOfMemoryException erhält.

angreifer

Das bedeutet meine rekursive Methode ruft sich immer wieder selber auf und setzt dann einfach, wenn sie bei 0 angekommen ist für aN ein, weil ich ja für aN = gesagt habe, dass es 1 sein soll. Und dann macht die Methode dann so lange bis wieder der in die Konsole eingegebene Wer für aN erreicht ist?
Ist dann aN mein Abrruchkriterium oder wo steckt das??

mogel

angreifer schrieb:

Das bedeutet meine rekursive Methode ruft sich immer wieder selber auf und setzt dann einfach, wenn sie bei 0 angekommen ist für aN ein, weil ich ja für aN = gesagt habe, dass es 1 sein soll. Und dann macht die Methode dann so lange bis wieder der in die Konsole eingegebene Wer für aN erreicht ist?
Ist dann aN mein Abrruchkriterium oder wo steckt das??

richtig ... in dem Moment springt alle wieder zurück ... Du kannst Dir doch in der Methode noch entsprechenden Infos ausgeben lassen

// double und int ??
static double Fakultät_Rekur(int aN)
{
    Console::WriteLine("starte Aufruf mit aN = {0}", aN);
    double ergebnis;
    if (aN == 0)
    {
        // Abbruchbedingung
        return 1.0;
    } else
    {
        //Rekursive Vereribarung
        ergebnis  = aN*Fakultät_Rekur(aN-1); //Eingegebene Zahl *
    }
    // das return gehört eigentlich hier hin
    Console::WriteLine("beende Aufruf mit aN = {0}  -->  ergebnis = {1}", aN, ergebnis);
    return ergebnis;
}

ach ja ... Rekursion mal anders erklärt -> http://www.google.de/search?q=rekursion

Bashar

Das ist doch einfach eine 1:1-Implementierung der Definition der Fakultät:
0! = 1
n! = n*(n-1)! (für n>0)

Wenn man mit der Definition Schwierigkeiten hat, hilft es vielleicht, sich das so zu überlegen:

n! = n*(n-1)(n-2)...*2*1 = n*[(n-1)(n-2)...*2*1] = n*(n-1)!

Ich hatte solange Angst vor Rekursion, bis ich aufgehört habe, mir den Ablauf des Hin- und Herspringens und den Aufbau des Stacks währenddessen vorzustellen. Für eine rekursive Lösung eines Problems braucht es zwei Dinge:

Einen Basisfall. Eine besonders kleine Version des Problems, für die man direkt die Lösung angeben kann. Beispiel: 0! = 1. Länge der leeren Liste = 0, Höhe des leeren Baumes = 0 und ähnliches
Eine Möglichkeit, einen komplexeren Fall auf die Lösung einfacherer Fälle zurückzuführen. Berechnung der Fakultät von n, indem ich zuerst die Fakultät von n-1 berechne. Berechnung der Länge einer Liste, indem ich den Kopf der Liste abhänge und die Länge der Restliste berechne. Berechnung der Höhe eines Baumes, indem ich zunächst die Höhen aller Nachfolger bestimme.

Der entscheidende Punkt ist: Man tut so, als würde die Funktion, die man gerade schreibt, den einfacheren Fall schon lösen können. An der Stelle muss man einfach mal loslassen können

Die Analogie zur mathematischen Induktion ist übrigens nicht zufällig!