Не могу понять эту проблему рекурсии дерева - PullRequest
Новая
       32

Не могу понять эту проблему рекурсии дерева

0 голосов
/ 01 октября 2019

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

Упражнение:

Я хочу поднятьсялестничный пролет, который имеет n ступеней. Я могу сделать 1 или 2 шага каждый раз. Сколько разных способов я могу подняться по этому лестничному пролету?

Ответ был:

Например, в случае, когда nis 5, есть 8 возможных путей:

1 1 1 1 1

2 1 1 1

1 2 1 1

1 1 2 1

1 1 1 2

1 2 2

2 1 2

2 2 1

И этот блок кода у меня возникли проблемы с его полным пониманием: 

(define (count-stairs n)
  (cond [(= n 1) 1]
        [(= n 2) 2]
        [else (+ (count-stairs (- n 1))
                 (count-stairs (- n 2)) ]) ))

Изображение, иллюстрирующее процесс

enter image description here

Моя проблема в том, почему есть знак +? разве счет-лестница (4) + счет-лестница (3) не дает 7 шагов? или я что-то здесь упускаю

ТАКЖЕ: вот полная ссылка на упражнение https://berkeley -cs61as.github.io / учебник / tree-recursion.html

пожалуйста, нужна ваша помощь!

1 Ответ

2 голосов
/ 01 октября 2019

Древовидная диаграмма просто дает пространство вызовов функций и их аргументов, которые начинаются с (count-stairs 5). Когда мы вызываем функцию с аргументом 5, она будет вызывать (count-stairs 4) из-за выражения (count-stairs (- n 1)) и будет вызывать (count-stairs 3) из-за выражения (count-stairs (- n 2)). Конечно, эти значения добавляются с +, который становится возвращаемым значением вызова. Дерево просто не отображает информацию о возвращаемом значении, только аргументы вызова.

(count-stairs 5) не означает «считать пять ступеней», но «вызывает функцию count-stairs с аргументом 5 дляпосчитайте, сколько существует разных способов подняться на лестницу 5 по лестнице ".

Для (count-stairs 3) результат будет 3, потому что (count-stairs 1) и (count-stairs 2) просто возвращают 1 и 2 соответственно.

Однако (count-stairs 4) добавляет (count-stairs 3) и (count-stairs 2), поэтому (count-stairs 4) -> 5.

Мы можем использовать эту обозначение стрелки, чтобы аннотировать выражения в дереве с их значениями результата, начиная снизу и работая вверх. В верхней части дерева мы получим (count-stairs 5) -> 8.

count-stairs - это лишь небольшое изменение скрытой рекурсивной функции Фибоначчи.

Почему это вычисляет числоспособы подняться по лестнице, используя 1 или 2 размера шага? Во-первых, базовые случаи понятны. Если у лестницы один шаг, есть только один способ пройти ее: мы делаем этот шаг. Итак (count-stairs 1) -> 1. Если есть два шага, то есть два пути: сделать каждый шаг или сделать оба шага в один шаг. Таким образом (count-stairs 2) -> 2. Тогда прибывает хитрая индуктивная часть. Если мы сталкиваемся с тремя или более лестницами, каково решение?

Если мы сталкиваемся с лестницей с n ступенями, n> 2, то у нас есть две возможности о том, как начать восхождение. Возможность (1): мы можем сделать один шаг, а затем подняться по оставшейся лестнице из n - 1 ступеней;или, возможность (2), мы можем сделать два шага как один шаг, а затем подняться по оставшейся лестнице из n - 2 шагов. Таким образом, количество способов восхождения на n ступеней является суммой путей из этих двух возможностей: количество способов восхождения на n - 1 ступеньку плюс количество способов восхождения на n - 2 ступени.

...