Was ist und ist keine Rekursion?

Question

Ich versuche zu verstehen, was genau Rekursion ist und konnte keine Antwort auf das Folgende finden.

Mein aktuelles Verständnis von Rekursion ist, dass es sich jederzeit eine Methode nennt.

I.E

Menu() 
{ 
if(i<2) 
{Console.WriteLine();} 
else 
{Menu();}  
} 

Das Vorstehende ist ein Beispiel für die Rekursion Aufruf einer Methode selbst.

Was ich bin mir nicht sicher über ein Szenario wie ist:

Menu() 
{ 
if(i<2) 
{Console.WriteLine();} 
else 
{Console.WriteLine("Something Went Wrong!"); MenuError();}  
} 

MenuError() 
{ 
Console.WriteLine("Something went wrong!"); 
Menu(); 
} 

Wenn die Methode eine Methode aufruft, die dann ruft es diese noch Rekursion?

Answer 1

Mein aktuelles Verständnis von Rekursion ist, dass es sich jederzeit eine Methode nennt.

Das ist richtig. Rekursive Definitionen sind selbstverweisende Definitionen.

Zwei interessante Eigenschaften rekursiver Definitionen sind Produktivität und Terminierung. Ein Programm ist produktiv, wenn es weiterhin Ausgaben liefert, obwohl die volle Ausgabe niemals kommen kann (daher kann es nicht enden). Ein Programm wird beendet, wenn es seine volle Ausgabe in endlicher Zeit liefert.

Zum Beispiel ist dies ein produktives, nicht-Abschlussprogramm:

Naturals(int i) { 
    Console.WriteLine(i); 
    Naturals(i + 1); 
} 

Dies ist ein Abschlussprogramm:

UpToTen(int i) { 
    Console.WriteLine(i); 
    if (i < 10) UpToTen(i + 1); 
} 

Dies ist ein nicht-produktives Programm:

DoNothing() { 
    DoNothing(); 
} 

---

Wenn Menu Anrufe MenuError und MenuError Anrufe Menu, wird dies manchmal gegenseitige Rekursion genannt. Der einzige Unterschied ist unsere Organisation; wir können den Code umschreiben, um nur eine Methode zu haben, indem wir MenuError einreihen.

Menu() { 
    if (i < 2) { 
    Console.WriteLine(); 
    } 
    else { 
    Console.WriteLine("Something Went Wrong!"); 
    Console.WriteLine("Something went wrong!"); 
    Menu(); 
    } 
} 

Sie können in der Tat abstrakt Rekursion selbst:

// General definition 
A Fix<A>(Func<Func<A>,A> f) { 
    return f(() => Fix(f)); 
} 

// Special definition for void functions 
void Fix(Action<Action> f) { 
    f(() => Fix(f)); 
} 

void Menu(Action menu) { 
    if (i < 2) { 
    Console.WriteLine(); 
    } 
    else { 
    Console.WriteLine("Something Went Wrong!"); 
    Console.WriteLine("Something went wrong!"); 
    menu(); 
    } 
} 

Fix(Menu); 

Hier ist ein weiteres Beispiel Fix mit der Fakultäts-Funktion zu definieren.

Func<int, int> Fac(Func<Func<int, int>> fac) { 
    return i => i == 0 ? 1 : i * fac()(i - 1); 
} 

// Fix<Func<int, int>>(Fac) is the factorial function 

Sie fragen sich vielleicht, warum Fix die Signatur nicht A Fix<A>(Func<A,A> f) stattdessen haben. Dies liegt daran, dass C# eine strikte Sprache ist, dh Argumente werden ausgewertet, bevor die Funktionsanwendung ausgewertet wird. Mit der einfacheren Signatur würde das C# -Programm in unendlicher Rekursion enden.

Answer 2

Ja, es ist immer noch Rekursion. Es gibt verschiedene Arten der Rekursion wie Tail-Rekursion, Baumrekursion usw. Sie können google für Ruhe auschecken.

Übrigens, wenn der Wert von i größer als oder gleich 2 ist, erhalten Sie Stapelüberlauffehler, da jeder einen anderen aufrufen wird.