Объясните: функция возвращает ту же функцию в го

Question

func main() {
    go spinner(100 * time.Millisecond)
    const n = 45
    fibN := fib(n) // slow
    fmt.Printf("\rFibonacci(%d) = %d\n", n, fibN)
}

func spinner(delay time.Duration) {
    for {
        for _, r := range `-\|/` {
            fmt.Printf("\r%c", r)
            time.Sleep(delay)
        }
    }
}

func fib(x int) int {
    if x < 2 {
        return x
    }
    return fib(x-1) + fib(x-2)
}

Вы можете объяснить вышеприведенную функцию fib, как получены результаты.

Функция fib возвращает вызовы fib, как приходят конечные результаты?

Answer 1

Ключ находится в этой функции:

func fib(x int) int {
    if x < 2 {
        return x
    }
    return fib(x-1) + fib(x-2)
}

Если x<2, функция немедленно возвращается, если нет, она возвращает результат вызова fib с меньшим значением x

Для рекурсивных вызовов есть 3 закона рекурсии:

1. У рекурсивного алгоритма должен быть базовый случай.
2. Рекурсивный алгоритм должен изменить свое состояние и двигаться в направлениибазовый случай.
3. Рекурсивный алгоритм должен вызывать сам себя рекурсивно.

http://interactivepython.org/courselib/static/pythonds/Recursion/TheThreeLawsofRecursion.html

В вашем примере базовый случай - это когда x < 2.Изменение состояния - это уменьшение на 1 или 2, и ваша функция вызывает себя рекурсивно, поэтому соблюдаются три закона.