#3: сорекурсивная реализация алгоритма Фибоначчи.

Приветствую читатель!

Сегодня оставлю здесь сорекурсивную реализацию алгоритма Фибоначчи на Kotlin. Обратите внимание на ключевое слово tailrec. Позволяет задействовать механизм оптимизации для хвостовой рекурсии. Под оптимизацией понимается условное представление функции плоским циклом.

Листинг из книги: Пьер-Ив Симон: Волшебство Kotlin

Kotlin

import java.math.BigInteger

fun main() {
    // return 55
    println( fibonacci(10) )
}

fun fibonacci(n: Int): BigInteger {
    tailrec fun fibonacci(val1: BigInteger, val2: BigInteger, acc: BigInteger): BigInteger = when {
        (acc == BigInteger.ZERO) -> BigInteger.ONE
        (acc == BigInteger.ONE) -> val1 + val2
        else -> fibonacci(val2, val1 + val2, acc - BigInteger.ONE)
    }
    return fibonacci(BigInteger.ONE, BigInteger.ZERO, BigInteger.valueOf(n.toLong()))
}