Где памятка?

Question

Я учу Kotlin, и из книги у меня есть функция Фибоначчи, которая демонстрирует концепцию запоминания:

import java.math.BigInteger

fun <T> List<T>.head(): T =
    if (this.isEmpty())
        throw IllegalArgumentException("head called on empty list")
    else
        this[0]

fun <T> List<T>.tail(): List<T> =
    if (this.isEmpty())
        throw IllegalArgumentException("tail called on empty list")
    else
        this.subList(1, this.size)

fun <T, U> foldLeft(list: List<T>, z: U, f: (U, T) -> U): U {
    tailrec fun foldLeft(list: List<T>, acc: U, f: (U, T) -> U): U =
        if (list.isEmpty())
            acc
        else
            foldLeft(list.tail(), f(acc, list.head()), f)
    return foldLeft(list, z, f)
}

fun fibo(number: Int): String {
    tailrec fun fibo(
        acc: List<BigInteger>, acc1: BigInteger,
        acc2: BigInteger, x: BigInteger
    ): List<BigInteger> =
        when (x) {
            BigInteger.ZERO -> acc
            BigInteger.ONE -> acc + (acc1 + acc2)
            else -> fibo(
                acc + (acc1 + acc2), acc2, acc1 + acc2,
                x - BigInteger.ONE
            )
        }

    val list = fibo(
        listOf(),
        BigInteger.ONE, BigInteger.ZERO, BigInteger.valueOf(number.toLong())
    )
    return makeString(list, ", ")
}

fun <T> makeString(list: List<T>, separator: String): String =
    when {
        list.isEmpty() -> ""
        list.tail().isEmpty() -> list.head().toString()
        else -> list.head().toString() +
                foldLeft(list.tail(), "") { x, y -> x + separator + y }
    }

fun main(args: Array<String>) {

    println(fibo(5))

} 

Может кто-нибудь объяснить мне, где здесь запоминание?

Answer 1

Я ... я не думаю, что есть вообще-то.

Сначала я хотел написать, что параметр acc вспомогательной функции fibo (тот, у которого отмечены 4 параметра) на tailrec) в конечном итоге содержит предыдущие числа Фибоначчи, но на самом деле они не доступны для их извлечения, поэтому я не думаю, что это имеет значение. примечание: я сделал x Int, потому что это упрощает код, и вы не будете вычислять число Фибоначчи с индексом, не вписывающимся в Long в нормальное время даже с запоминанием):

fun fibo(x: Int): BigInteger {
    tailrec fun fibo(
        acc: List<BigInteger>, x: Int
    ): Pair<List<BigInteger>, BigInteger> =
        when {
            x < acc.size -> Pair(acc, acc[x])
            x == acc.size -> {
                val y = acc[x - 1] + acc[x - 2]
                Pair(acc + y, y)
            }
            else ->
                fibo(fibo(fibo(acc, x - 2).first, x - 1).first, x)
        }

    return fibo(listOf(BigInteger.ONE, BigInteger.ONE), x).second
}