Древовидная диаграмма просто дает пространство вызовов функций и их аргументов, которые начинаются с (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 ступени.