хвостовая рекурсия и фибоначчи

Question

Я смотрел на этом сайте: http://rosettacode.org/wiki/Fibonacci_sequence#JavaScript и увидел эту программу:

function fib(n) {
  return function(n,a,b) {
    return n>0 ? arguments.callee(n-1,b,a+b) : a;
  }(n,0,1);
}

Как это работает, чем эти два аргумента (а и б) помогают. Я проследил это и до сих пор не могу понять, как это работает

Answer 1

В function(n,a,b), n служит счетчиком обратного отсчета, а a b хранит два последовательных числа Фибоначчи с целью вычисления следующего, поэтому, когда n достигает 0, у вас есть a в качестве n + 1-го числа Фибоначчи (поскольку у настоящего Фибоначчи есть две 1 в качестве начала).

Например, n = 4:

n  a  b
4  0  1
3  1  2
2  2  3
1  3  5
0  5  8

Как видите, значения a и b всегда равны числам Фибоначчи. Кроме того, это очень похоже на функциональное программирование (как сказано на сайте Схема Программисты).

Answer 2

a и b представляют текущий номер последовательности и следующий номер последовательности, начиная с 0 и 1. n - таймер обратного отсчета, который указывает, какой элемент последовательности Фибоначчи будет возвращен (например, n = 10 вернет 55).

Эта функция работает, принимая аргумент n, что означает, что она будет вычислять n-е число последовательности:

function fib(n) {

Затем код определяет функцию, которая будет вычислять следующее число в последовательности:

function(n,a,b) {
  return n>0 ? arguments.callee(n-1,b,a+b) : a;
}

По сути, эта анонимная функция выполняет обратный отсчет n на единицу каждый раз, когда она выполняется, и в то же время перемещается a и b к следующим числам в последовательности. Если n равно 0, последовательность завершена, и возвращается текущий номер a.

arguments.callee относится к выполняемой в данный момент функции, так что код просто означает обратный вызов себя с новыми аргументами. Другими словами, для начала следующей итерации «цикла».

Наконец, говоря (n,0,1);, код фактически вызывает fib с параметрами n,0,1. Оператор return, который я исключил из приведенного выше фрагмента, принимает возвращаемое значение анонимной функции и возвращает его вызывающей стороне fib.

<ч />

Тем не менее, использование рекурсии таким образом неэффективно для таких языков, как JavaScript, которые не имеют оптимизации хвостового вызова. Для больших n было бы лучше написать это, используя стандартную циклическую конструкцию вместо рекурсии.

Answer 3

Как объяснено здесь , arguments.callee относится к текущей функции, в которой вы находитесь. Поскольку функция, в которой вы находитесь, является анонимной , это единственноеспособ вызова функции и достижения рекурсии.

Специальная функция вычисляет последовательность Фибоначчи путем рекурсивного вызова внутренней функции.

Answer 4

a и b - параметры новой анонимной функции.

Я бы посмотрел на эту страницу , которая является документацией об объекте arguments . В документации arguments.callee содержится ссылка на функцию, в которой вы сейчас находитесь. Это необходимо сделать, потому что они работают в анонимной функции, поэтому у нее действительно нет имени (о котором они знают).

Кажется, что они рекурсивно вызывают функцию, которую они (анонимно) определяют на глубину n. Попутно они вычисляют числа Фибоначчи и возвращают значение a после достижения глубины n. Начальные значения, переданные в функцию: (n,0,1)

Answer 5

Я вижу несколько проблем, которые могут привести к путанице. Оптимизация короткой руки и хвоста для рекурсивного шаблона функции.

Возможно, проблема в сокращенной версии кода. Переписано для ясности ниже.

1. подтверждение анонимной функции путем присвоения ей имени "recur"
2. условный (троичный) оператор расширен.

Оптимизация хвоста используется для приручения стека к использованию рекурсивных функций путем добавления части аккумулятора. Это обычная модель, но она лишает читабельности. Это функция recur .

Особое замечание: производительность велика по сравнению с повторением в цикле.

function fib(n) {
    function recur(n, a, b) {
        if (n > 0) {
            return recur(n - 1, b, a + b);
        } else {
            return a;
        }
    }
    return recur(n, 0, 1);
}

Что касается параметров, n - счетчик итераций, a и b - части последовательности Фибоначчи.