Никакая идея, как решить упражнение 1.11 SICP

Question

Никакая идея, как решить упражнение 1.11 SICP

Функция f определяется правилом это f(n) = n если n < 3 и f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) если n > 3. Запишите процедуру, которая вычисляет f посредством рекурсивного процесса. Запишите процедуру, которая вычисляет f посредством итеративного процесса.

Реализация его рекурсивно достаточно проста. Но я не мог выяснить, как сделать это многократно. Я пытался соответствовать данному примеру Fibonacci, но я не знал, как использовать его в качестве аналогии. Таким образом, я сдался (позор мне) и Погугленный для объяснения, и я нашел это:

(define (f n)
   (if (< n 3)
       n
       (f-iter 2 1 0 n)))

(define (f-iter a b c count)
   (if (< count 3)
       a
       (f-iter (+ a (* 2 b) (* 3 c))
               a
               b
               (- count 1))))

После чтения его я понимаю код и как это работает. Но то, что я не понимаю, является процессом, должен был добраться из рекурсивного определения функции к этому. Я не добираюсь, как код, возможно, сформировался в чьей-то голове.

Вы могли объяснить, что мыслительный процесс должен был найти решение?

25

recursion scheme iteration sicp

задан Will Ness 15 February 2018 в 18:13

2 ответа

Поскольку в посте, на который вы ссылаетесь, описано многое о решении, я постараюсь дать только дополнительную информацию.

Здесь вы пытаетесь определить хвостовую рекурсивную функцию в Scheme, учитывая (нехвостовое) рекурсивное определение.

Базовый случай рекурсии (f(n) = n, если n < 3) обрабатывается обеими функциями. Я не совсем понимаю, зачем автор это делает; первая функция могла бы быть просто:

(define (f n)
   (f-iter 2 1 0 n))

Общая форма была бы такой:

(define (f-iter ... n)
   (if (base-case? n)
       base-result
       (f-iter ...)))

Обратите внимание, что я пока не заполнил параметры для f-iter, потому что сначала нужно понять, какое состояние нужно передать от одной итерации к другой.

Теперь давайте посмотрим на зависимости рекурсивной формы f(n). Она ссылается на f(n - 1), f(n - 2) и f(n - 3), поэтому нам нужно сохранить около этих значений. И, конечно, нам нужно значение самого n, чтобы мы могли прекратить итерации по нему.

Вот так и получается хвостовой рекурсивный вызов: мы вычисляем f(n) для использования в качестве f(n - 1), поворачиваем f(n - 1) к f(n - 2) и f(n - 2) к f(n - 3) и уменьшаем счет.

Если это все равно не поможет, пожалуйста, попробуйте задать более конкретный вопрос - очень трудно ответить, когда вы пишете "я не понимаю", имея уже относительно подробное объяснение.

4

ответ дан 28 November 2019 в 20:33

Другие вопросы по тегам:

recursion scheme iteration sicp

Похожие вопросы:

score 32 · Accepted Answer

Вам нужно фиксировать состояние в некоторых аккумуляторах и обновлять состояние на каждой итерации.

Если у вас есть опыт работы с императивным языком, представьте, что вы пишете цикл while и отслеживаете информацию в переменных во время каждой итерации цикла. Какие переменные вам понадобятся? Как бы вы их обновляли? Именно это нужно сделать, чтобы выполнить итеративный (хвостовой рекурсивный) набор вызовов в Scheme.

Другими словами, может помочь начать думать об этом как о цикле while вместо рекурсивного определения. В конце концов, вы достаточно хорошо освоите рекурсивные -> итеративные преобразования, чтобы не нуждаться в дополнительной помощи для начала работы.

В этом конкретном примере вам придется внимательно рассмотреть три вызова функций, потому что не сразу понятно, как их представить. Однако вот вероятный ход мыслей: (в псевдокоде Python, чтобы подчеркнуть императивность)

Каждый рекурсивный шаг отслеживает три вещи:

f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)

Таким образом, мне нужны три части состояния для отслеживания текущего, последнего и предпоследнего значений f. (то есть, f(n-1), f(n-2) и f(n-3)). Назовем их a, b, c. Я должен обновлять эти части внутри каждого цикла:

for _ in 2..n:
    a = NEWVALUE
    b = a
    c = b
return a

Так что же такое NEWVALUE? Ну, теперь, когда у нас есть представления f(n-1), f(n-2) и f(n-3), это просто рекурсивное уравнение:

for _ in 2..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

Теперь осталось только выяснить начальные значения a, b и c. Но это легко, поскольку мы знаем, что f(n) = n, если n < 3.

if n < 3: return n
a = 2 # f(n-1) where n = 3
b = 1 # f(n-2)
c = 0 # f(n-3)
# now start off counting at 3
for _ in 3..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

Это все еще немного отличается от итерационной версии схемы, но я надеюсь, что теперь вы видите ход мысли.