Дерево и рекурсия по форме данных
Дерево задает один и тот же вопрос в каждом узле. Пуст ли этот элемент, является ли он еще одной парой для обхода или листом для преобразования?
Как одна процедура работает на любой глубине дерева?
- Распознавание случаев листьев и ветвей
- Перестроение дерева с сохранением его формы
- Использование структурной рекурсии вместо фиксированной глубины
scale-tree не считает уровни. Встречая пару, процедура применяет ту же процедуру к обеим ее частям. Встречая лист, она выполняет числовую операцию.
Структура управления отражает определение данных. Благодаря этому соответствию процедура работает как с неглубоким списком, так и с глубоко вложенным деревом без отдельных ветвей для каждой глубины.
- Вывод
- —
- Значение
- —
- Диагностика
- —
Первая программа возвращает (10 (20 (30 40) 50) (60 70)).
Найдите места, где процесс ветвится на обработку car и cdr. Итоговая вложенность представляет собой запись этих повторяющихся структурных решений. Трасса выполнения точно фиксирует все структурные ветвления в выбранном запуске.
Измените программу и сравните результат.
Определите count-leaves. Процедура должна возвращать 0 для пустого списка, складывать результаты обеих ветвей для пары и возвращать 1 для любого другого листа.
Показать подсказку
Используйте такое же тройное разделение случаев, как в scale-tree, но измените операцию над листом.