Visual Basic .NET: Fibonaccifolge


Code:  

Private Function FiboRek(ByVal Value As Integer) As Integer
    If Value = 1 Or Value = 2 Then Return 1
    Return FiboRek(Value - 1) + FiboRek(Value - 2)
End Function

Private Function FiboIter(ByVal Value As Integer) As Integer
    If Value = 1 Or Value = 2 Then Return 1
    Dim Werte(Value) As Integer
    Werte(1) = 1
    Werte(2) = 1
    For Zähler As Integer = 3 To Value
        Werte(Zähler) = Werte(Zähler - 1) + Werte(Zähler - 2)
    Next
    Return Werte(Value)
End Function

Erklärung Bearbeiten

Die rekursive Implementierung ist auch hier die einfachere. Zuerst definieren wir mit den gegebenen Basiswerten den Rekursionsanfang: Das erste und zweite Glied der Fibonaccifolge sind 1. Davon ausgehende Werte errechnen sich als die Summe der beiden vorhergehenden Werte; das n-te Glied der Fibonaccifolge ist die Summe des (n-1)-ten Gliedes und des (n-2)-ten Gliedes.

Die iterative Implementierung ist da schon komplexer. Auch hier die beiden Elemente 1 und 2 sofort zurückzugeben, hat sich für die folgende Implementation als am zweckmäßigsten erwiesen. Da, anders als bei der Fakultät, ein Wert zweimal gebraucht wird, nämlich für die Berechnung der zwei nächsten Werte, ist es nicht möglich, eine einzelne Variable als Rechenraum zu nutzen. Ich habe mich hier deshalb für ein Feld entschieden. Das Element 0 des Feldes wird nicht genutzt, um den Code einfach zu halten. Element 1 und 2 werden mit den geg. Werten belegt. Die folgenden Felder werden mit einer Schleife berechnet, die schrittweise von den einfacheren zu den komplexeren Problemen übergeht. In der Schleife werden dann die einzelnen Werte so berechnet, dass das Element n des Feldes immer das n-te Glied der Fibonaccifolge ist. Zum Schluss wird dann das gesuchte Element zurückgegeben.