Bei der Verwendung von Java/Kotlin für die Programmierung wird empfohlen, Tail-Rekursion oder die Iterative Version zu verwenden? Gibt es einen Unterschied in der Leistung?

Question

Ich versuche, über gute Praktiken in der Programmierung zu lernen, und ich bin mit dieser Frage festgefahren. Ich weiß, dass rekursive Funktionen in Java (manchmal) "ein Schmerz im Arsch" sein können, und ich versuche, so viel wie möglich die Endversion dieser Funktion zu implementieren. Ist es das wert, sich damit zu befassen, oder sollte ich das auf altmodische Weise machen? Gibt es einen Unterschied zwischen diesen beiden Funktionen (in Kotlin):

tailrec fun tail_fibonacci(n : BigInteger, fib1 : BigInteger = BigInteger.ZERO , fib2 : BigInteger = BigInteger.ONE) : 
BigInteger { 
    return when(n){ 
     BigInteger.ZERO -> fib1 
     else -> tail_fibonacci(n.minus(BigInteger.ONE),fib1.plus(fib2),fib1) 
    } 
} 

fun iterative_fibonacci(n: BigInteger) : BigInteger { 
    var count : BigInteger = BigInteger.ONE 
    var a : BigInteger = BigInteger.ZERO 
    var b : BigInteger = BigInteger.ONE 
    var c : BigInteger 
    while(count < n){ 
     count += BigInteger.ONE 
     c = a + b 
     a = b 
     b = c 
    } 
    return b 
} 

Answer 1

Der größte Unterschied, den ich sehe, ist die Signaturen: während iterative_fibonacci ein Argument und ist ziemlich klar, tail_fibonacci dauert drei, und obwohl die Standardeinstellungen bereitgestellt werden, könnte dies den Benutzer überraschen. Sie können jedoch eine Wrapper-Funktion dafür erstellen und sogar die tailrec-Funktion zu local one machen.

Es sollte nicht viel Unterschied in der resultierenden Bytecode die beiden Funktionen zusammengestellt, mit Ausnahme von n.minus(BigInteger.ONE) vs count += BigInteger.ONE, und Sie können es mit a Kotlin bytecode viewer selbst überprüfen. In Bezug auf die Leistung sollte es keinen vorhersehbaren Unterschied zwischen den beiden Implementierungen geben (beachten Sie auch, dass die JVM den Code zur Laufzeit mit dem JIT-Compiler optimiert), aber natürlich ist die tailrec-Funktion viel effizienter als eine gewöhnliche rekursive Funktion wäre.

In Bezug auf den Code-Stil (der sehr meinungsbasiert ist), sehen viele tail-rekursive Lösungen natürlicher aus (und näher an der mathematischen Notation), und manche nicht (zB wenn viele Parameter in einem enden komplettes Durcheinander). Ich denke, tailrec sollte als ein Leistungstool verwendet werden (und insbesondere als eine Möglichkeit, Stapelüberlauf zu vermeiden, der alle rekursiven Aufrufe zu Tailern erfordert), wenn Sie eine rekursive Definition finden, die besser geeignet ist, um das auszudrücken Code tut es.

Answer 2

Sie in Bezug auf Leistung gleichwertig sind. Kotlin wird die Rekursion auf Tailrec-Funktionen optimieren, was bedeutet, dass es mit einem Loop-basierten Ansatz identisch ist.

Ob Sie einen funktionalen oder iterativen Ansatz bevorzugen, hängt letztlich von Ihren eigenen Präferenzen (und gegebenenfalls von Ihrem Team) ab und berücksichtigt Lesbarkeit, Prägnanz und Intuitivität. Diese Beurteilung kann sich von Methode zu Methode ändern; Eine Funktion könnte mit einem funktionalen Ansatz besser lesbar sein, während eine andere von einer einfachen Schleife profitieren könnte.

Das Schöne an Kotlin ist, dass es beide Ansätze unterstützt und es einem Entwickler ermöglicht, das Werkzeug zu verwenden, das er für den Job benötigt.