gibt es jemals eine Zeit, die Sie lieber nicht verwenden würde die Rekursion?

Ich habe ein problem, für ein Uni-Labor;

Schreiben Sie ein kurzes Programm, dass die Ausgänge alle möglichen Zeichenfolgen, die mithilfe von Zeichen 'c', 'a', 'r', 'b', 'o' und 'n' genau einmal.

Scheint es sich um ein gemeinsames interview-Frage und gut dokumentiert.

Also habe ich codiert es mit Java eine rekursive Methode, die nicht allzu schwer, , Wann oder warum würden Sie nicht wählen, Rekursion zu verwenden, und was wäre der einfachste Weg, es zu tun?

Begann ich zu code einen Zähler, wäre ein count-down auf Basis 6, der Ausgang wäre dann die Referenz char ' s, und drucken Sie die Zeichenfolge.

Dank,

  • Nie, nie, nie nicht verwenden Rekursion. 😉
  • FYI: nicht davon ausgehen, tail recursion ist optimiert für die JVM: stackoverflow.com/questions/105834/...
  • Um zu bestimmen, ob es angebracht ist, Rekursion zu verwenden, müssen Sie sich Fragen, ist es angebracht, Rekursion zu verwenden?
InformationsquelleAutor LewisMc | 2010-09-23
  1. 15

    Ja, es gibt viele Zeiten würde ich nicht verwenden Rekursion. Rekursion ist nicht kostenlos, hat es eine Kosten im Stapelspeicher und das kann oft viel mehr begrenzte Ressource, als einige andere. Es gibt auch eine Zeit Kosten, jedoch kleiner, im Aufbau-und Abbau-stack-frames.

    Beispiel die viel gepriesene faktorielle Funktion ist eine, wo ich würde wahrscheinlich entscheiden Sie sich für einen iterativen Ansatz, bei dem die zahlen waren groß. Die Berechnung von 10000! mit:

    def factorial (n):
    if n = 1 return 1
    return n * factorial (n-1)

    verwenden von 10.000 stack frames (vorausgesetzt, es ist nicht optimiert durch den compiler in eine iterative Lösung natürlich), eine ganze Menge. Die iterative Lösung:

    def factorial (n)
    r = 1
    while n > 1:
        r = r * n
        n = n - 1
    return r

    verwenden nur den einen stack-frame, und wenig anderes.

    Es ist wahr, dass sich rekursive Lösungen sind oft eleganter code, aber Sie haben Temperament, die mit den Beschränkungen Ihrer Umwelt.

    Ihre carbon ist nur ein Beispiel, wo ich hätte eigentlich Rekursion seit:

    • es nutzt höchstens sechs stack-frames (eine pro Zeichen im string); und
    • es relativ elegant, zumindest viel mehr als sechs verschachtelte Schleifen und große Gleichheit überprüft.

    Zum Beispiel den folgenden Python-code funktioniert der trick:

    def recur (str, pref = ""):
    # Terminating condition.

    if str == "":
        print pref
        return

    # Rotate string so all letters get a chance to be first.

    for i in range (len (str)):
        recur (str[1:], pref + str[:1])
        str = str[1:] + str[:1]

recur ("abc")

    Herstellung:

    abc
acb
bca
bac
cab
cba

    Natürlich, wenn der string kann 10K lang, würde ich überdenken, da das würde eine Menge mehr stack-Ebenen, aber, vorausgesetzt, Sie halten in der niedrig genug ist, die Rekursion ist eine praktikable Lösung.

    • Tail-Rekursion ist genauso wirksam wie eine Rekursion der kostenlosen version. Und in diesem speziellen Fall ist die Rekursion die am besten geeignete Lösung.
    • das stimmt nur, wenn es tatsächlich optimiert. Tail-end-Rekursion kann sein, aber manchmal sind die Entscheidungen, wenn recurse komplexer sind.
    InformationsquelleAutor paxdiablo
  2. 6

    Rekursion, wenn Ihre Daten inhärent hierarchischen/verschachtelten. Verwenden Sie die iteration, wenn Ihre Daten linear/flach.

    In Ihrem Fall, es ist eine Natürliche der Bestellung können Sie verhängen auf die Kombinationen, so dass Sie behandeln können die Daten als linear, aber wenn Sie es als einen Baum, den Sie am Ende mit dem rekursiven Ansatz.

    Wenn die Struktur Ihres Algorithmus widerspiegelt die Struktur des zugrunde liegenden Problems, Sie am Ende mit einfacher code, der leichter zu verstehen ist. Keine Rekursion, nur weil Ihr CS201 professor dachte, es war So! Cool!

    InformationsquelleAutor Alex Feinman
  3. 5

    Einfach eine Schleife verwenden und vermeiden Sie die Verwendung von Rekursion. Rekursion wird in der Regel vermieden, weil es macht den code weniger lesbar und schwerer zu pflegen und zu Debuggen. Wenn Sie über geringe Ressourcen als paxdiablo sagte Stapelspeicher könnte für Sie nützlich sein, so sollten Sie vermeiden, mit der es dann auch.

    • "Rekursion ist in der Regel vermieden, weil es macht den code weniger lesbar und schwerer zu pflegen und debug" - Das scheint eine ziemlich grobe Verallgemeinerung. Mit einigen mathematischen hintergrund, rekursive Lösungen können ziemlich lesbar. Iterative Ansätze sind in der Regel ein zu-Maschine-centric zu Zeiten, die kann ein wenig langweilig zu Lesen, manchmal.
    • -1 ich Stimme nicht zu mit die erste Hälfte der Antwort, vor allem, wenn eine so kühne Aussage (dass die Rekursion vermieden wird), ist nicht gesichert durch einen Verweis von einer Art sein.
    • In der Tat, es gibt Zeiten, zu verwenden recusion und mal nicht, man muss sich auf jeden Fall auf seinen eigenen Verdiensten. Oft eine iterative Lösung benötigt deutlich mehr code für wenig bis keinen Gewinn.
    InformationsquelleAutor Numenor
  4. 4

    Algorithmen und Datenstrukturen von Niklaus Wirth einen Abschnitt "Wenn Sie nicht zu benutzen Rekursion", aber Rekursion ist nützlich für Programmierer-tool. Ich denke, dass das Verständnis der Rekursion ist "muss" für Programmierer.

    Haben Sie ein kluger Ansatz, um permutation problem. Es kann gelöst werden rekursiv (pseudocode):

    private void PermutationsRecursive(string prefix, string s)
{
    int N = s.Length;

    if (N > 0)
        for (int i = 0; i < N; i++)
            PermutationsRecursive(prefix + s[i], s.Substring(0, i) + s.Substring(i + 1, N - i - 1));
    else
        WriteLine(prefix);
}

PermutationsRecursive("", "carbon");
    InformationsquelleAutor Branimir
  5. 2

    Wenn es viele Aufrufe von Rekursion dann ist dein stack können explodieren, so dass Sie mit StackOverflowError. Das gute Beispiel ist die Berechnung der Fibonacci-zahlen (oder die Türme von Hanoi-problem) mit basic
    Rekursion Sie werden nicht in der Lage zu berechnen, viele von denen zahlen. Was werden Sie in der Lage, durch die Verwendung von nicht wiederkehrenden version. Im Grunde Rekursion erzeugt gut aussehende Lösung und diese ist eine Tugend. Sie kann sich noch gut arbeiten, Rekursion Lösung mit tail-Rekursion

    InformationsquelleAutor Gadolin
  6. 2

    Wie die Leute oben geschrieben haben, die Rekursion ist nicht immer die optimale Lösung (Funktion Anrufe können teuer sein, und Sie verbrauchen den stack, es sei denn der compiler kann optimieren tail recursion entfernt). Es ist jedoch besonders geeignet, um solche Probleme wie deine.

    Während theoretisch ist es möglich Ausdrücken, jeder rekursive Algorithmus in Bezug auf die iteration (ex. durch die manuelle Simulation des call-stack mit einem array) und manchmal die äquivalente iterative Lösung ist weniger elegant. Hier ist ein Beispiel: 

    
text = 'carbon'
n = len(text)
for permutation_i in range(factorial(n)):
    free_letters = list(text)
    divisor = 1
    for character_i in range(n, 0, -1):
        letter = free_letters.pop(permutation_i//divisor%character_i)
        print(letter, end='')
        divisor *= character_i
    print()

    InformationsquelleAutor Marek Rocki
Schreibe einen Kommentar