SICP решение Фибоначчи, установите `a + b = a`, почему бы не` a + b = b`?

Question

Я читаю Дерево Рекурсия SICP, где fib было вычислено с помощью линейной рекурсии.

Мы также можем сформулировать итерационный процесс для вычисления чисел Фибоначчи. Идея состоит в том, чтобы использовать пару целых чисел a и b , инициализированных Fib (1) = 1 и Fib (0) = 0 , и многократно применять одновременные преобразования

Нетрудно показать, что после применения этого преобразования n раз, a и b будут равны, соответственно, Fib (n + 1) и Fib (n). Таким образом, мы можем вычислять числа Фибоначчи итеративно, используя процедуру

(переписать Emacs Lisp вместо Scheme)

#+begin_src emacs-lisp :session sicp 
(defun fib-iter (a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

(defun fib (n)
  (fib-iter 1 0 n))

(fib 4)
#+end_src

"Set a + b = a и b = a ", мне трудно обдумать это.

Общая идея найти fib проста:

Предположим, что заполненная таблица чисел Фибоначчи, найдите X в таблице, шаг за шагом перейдя от 0 к X.

Решение едва интуитивно понятно.

Разумно установить a + b = b, a = b:

(defun fib-iter (a b count)
  (if (= count 0)
      a
      (fib-iter b (+ a b) (- count 1))
  )
)
(defun fib(n)
  (fib-iter 0 1 n))

Таким образом, настройка авторов кажется не более чем анти-интуитивным размещением b в голове безспец. Назначение.

Однако я, безусловно, признаю, что SICP заслуживает того, чтобы копать глубже и глубже.

Какие ключевые моменты я упускаю? Зачем устанавливать a + b = a, а не a + b = b?

Answer 1

Повторение дано в императивной форме. Например, в Common Lisp мы могли бы использовать параллельное присваивание в теле цикла:

(psetf a (+ a b) 
       b a)

Чтобы уменьшить путаницу, мы должны подумать об этом функционально и дать старое и новоепеременные с разными именами:

a = a '+ b'

b = a '

Это уже не присвоение, а пара равенств;мы оправданы в использовании обычного математического оператора « = » вместо стрелки присваивания.

Линейная рекурсия делает это неявно, потому что избегает присваивания. Значение выражения (+ a b) передается как параметр a. Но это новый экземпляр a в новой области видимости, который использует то же имя, а не присвоение;привязка просто приводит к тому, что эти два значения эквивалентны.

Мы можем увидеть это также с помощью «правила скольжения Фибоначчи»:

    1  1  2  3  5  8  13
    ----------------------------- <-- sliding interface
             b' a' 
                b  a

Когда мы вычисляем последовательность,это окно с двумя числами, записи которого мы называем a и b , которое скользит по последовательности. Вы можете прочитать равенства в любой позиции непосредственно из правила скольжения: посмотрите, b = a ' = 5 и a = b' + a ' = 8.

Вас может смутить a , ссылаясь на более высокое положение в последовательности. Возможно, вы думаете об этой маркировке:

    1  1  2  3  5  8  13
    ------------------------
             a' b'
                a  b

Действительно, в соответствии с этим соглашением об именах, теперь у нас есть b = a ' + b' , как вы ожидаете, и a = b '.

Вопрос только в том, какая переменная обозначена как ведущая дальше по последовательности, икоторый является последним.

Соглашение " a ведет" исходит из того, что a предшествует b в алфавите,и поэтому он сначала получает более новые «обновления» из последовательности, которые затем передаются в b .

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

Answer 2

Насколько я понимаю, ваша проблема в том, что вам не нравится, что порядок аргументов для fib-iter не такой, как вы думаете. Ответ в том, что порядок аргументов функций очень часто просто произвольный и / или условный: это выбор, сделанный человеком, пишущим функцию. Это не имеет значения ни для кого, кроме человека, читающего или пишущего код: это стилистический выбор. Мне не особенно интуитивно понятно, что fib определено как

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter next current n)
  (if (zero? n)
      current
      (fib-iter (+ next current) next (- n 1))))

Вместо

(define (fib n)
  (fib-iter 0 1 n))

(define (fib-iter current next n)
  (if (zero? n)
      current
      (fib-iter (+ next current) current (- n 1))))

Есть случаи, когда это не так. Например, Стандартный Lisp (предупреждение, ссылка на PDF) определил mapcar, чтобы отображаемый список представлял собой аргумент first , а функция отображалась во втором. Это означает, что вы не можете расширить его так, как оно было расширено для более поздних диалектов, так что для него требуется любое положительное число списков с функцией, применяемой к соответствующим элементам всех списков.

АналогичноЯ думаю, что было бы крайне не интуитивно определять аргументы - или / наоборот.

, но во многих, многих случаях это просто вопрос выбора и следования ему.