Eine gute Auswahl an Rekursionslösungen in C/C++/Java/C#

Question

Ich sah diese Frage aber die Antworten dort sind nicht sehr relevant. Ein Freund braucht eine Sammlung von gelösten Rekursionsaufgaben, um für eine Prüfung zu lernen morgen .

Er hat das Thema theoretisch gelernt, hat aber Probleme, Rekursionsprobleme tatsächlich zu lösen. Kennen Sie eine gute Quelle für gelöste Rekursionsprobleme (vorzugsweise in C, aber auch in einer C-ähnlichen Sprache), die im Internet verfügbar ist?

Hinweis: Beispiele in funktionalen Sprachen sind hier nicht sehr hilfreich. Mein Freund befindet sich in einem Lernwettlauf, um morgen seine Prüfung zu bestehen, und ich bin sicher, dass der Wechsel der Sprachen ihn zu diesem Zeitpunkt nur verwirren wird (in anderen, weniger stressigen Zeiten könnte es lehrreich sein).

Answer 1

Eine der besten Möglichkeiten, die Rekursion zu erlernen, besteht darin, Erfahrungen in einer funktionalen Programmiersprache wie Haskell, Lisp oder Scheme zu sammeln.

Die Suche nach rekursiven Problemen kann also auf die Suche nach einigen Problemen und Antworten im Zusammenhang mit funktionalen Programmiersprachen reduziert werden. Hier ist ein Beispiel 99 Lisp-Probleme .

Es dauert wirklich nur 5 Minuten, Scheme oder Lisp zu lernen, so dass Sie sofort mit Beispielen für den von Ihnen erwähnten Test morgen beginnen können.

Eine weitere gute Möglichkeit, die Rekursion zu erlernen, besteht darin, sich in mathematischen Beweisen zu üben, die Induktion beinhalten.

---

Schlüsselbegriffe der Rekursion:

Bei der Rekursion muss man nicht wissen, wie das Problem zu lösen ist. Man muss nur 2 Dinge wissen. 1) wie man die kleinste Instanz des Problems löst, und 2) wie man es in kleinere Teile zerlegt.

Das heißt, Sie müssen sich nur vor Augen halten, dass Sie Folgendes brauchen: 1) einen Basisfall und 2) einen rekursiven Fall.

Der Basisfall behandelt eine einzige Instanz dessen, was Sie mit der kleinsten Eingabe machen wollen.

Der rekursive Fall zerlegt das Problem in ein Teilproblem. Schließlich wird dieses Teilproblem auf den Basisfall reduziert.

Ejemplo:

//1+...+n = n*n(+1)/2 = sumAll(n):

int sumAll(int x)
{
  if(x == 0) //base case
    return 0; 
  else
    return sumAll(x-1) + x; //recursive case
}

Es ist wichtig zu verstehen, dass es nicht schwer ist, den Basisfall herauszufinden. Er muss einfach nur existieren. Hier ist eine äquivalente Lösung für x> 0:

//1+...+n = n*n(+1)/2 = sumAll(n):
int sumAll(int x)
{
  if(x == 1) //base case
    return 1; 
  else
    return sumAll(x-1) + x; //recursive case
}

Answer 2

Dieser Artikel erklärt die Rekursion und enthält einige einfache C-Beispiele für das Durchlaufen von verknüpften Listen und Binärbäumen

Answer 3

Das wird sich wie eine sehr lahme Antwort anhören, aber Rekursion ist ein Paradigma, das für Anfänger oft sehr schwer zu begreifen ist. Ihr Freund wird mehr als einen Tag über das Thema nachdenken müssen, um das Konzept zu verstehen.

Vielleicht möchten Sie, dass er sich die Projekt Euler für eine mögliche Studienrichtung.

Answer 4

Ich denke, die Syntax von Haskell eignet sich hervorragend für rekursives Denken, weil das Konstrukt des Mustervergleichs den Basisfall und den rekursiven Fall so offensichtlich macht. Dies in eine andere Sprache zu übersetzen ist dann ziemlich einfach.

sumAll [] = 0
sumAll (x:xs) = x + sumAll xs

Um dies zu verstehen, müssen Sie eigentlich nur wissen, dass

• [] steht für eine leere Liste,
• (x:xs) zerlegt eine Liste in einen Kopf (x) und einen Schwanz (xs)

Sie müssen nicht alles über Haskell lernen (was, seien wir ehrlich, schwer ist) - aber einige der Grundlagen zu lernen, hilft Ihnen sicherlich, in Rekursionen zu denken.

Answer 5

In der Sprache C/C++ kann eine Funktion sich selbst aufrufen und dieser Fall wird Rekursion genannt. Hauptsächlich gibt es zwei Fälle von Rekursion:

1. Basisfall.
2. rekursiver Fall.

und wir haben einige rekursive Kategorien wie...

1. Rekursion der Liner
2. Binäre Rekursion
3. Verschachtelte Rekursion
4. Gegenseitige Rekursion
5. Schwanzrekursion

Hier ein Beispiel zur Diskussion der Rekursion ...

// a recursive program to calculate NcR  //
#include <stdio.h> 
int ncr(int x,int y)
{
    if(y>x)
    {
        printf("!sorry,the operation can't processed.");
        getch();
        exit(1);
    }
    else if(y==0 ||y==x)   //base case
    {
        return(1);
    }
    else
    {
        return(ncr(x-1,y-1)+ncr(x-1,y));  //recursive case
    }
}