двойная рекурсия

Общие вопросы: версии и диалекты, синтаксис языка, cтруктуры и типы данных (массивы, строки, списки...), обработка данных и т.д.
Ответить
ujif
Сообщения: 4
Зарегистрирован: 13 июн 2013, 19:27

двойная рекурсия

Сообщение ujif » 03 июл 2013, 18:36

помогите разобраться с двойной рекурсией
какие вызовы за какими следуют(с одинарной понятно)
например
procedure d(n:byte);
begin
if n=0 then exit
else
d(n-1);
d(n-1);
end;
n:=2;

Хыиуду
Сообщения: 2388
Зарегистрирован: 06 мар 2005, 21:03
Откуда: Москва
Контактная информация:

Re: двойная рекурсия

Сообщение Хыиуду » 04 июл 2013, 16:21

Проход по шагам (кнопка F8) вам в помощь
Искусство программирования - заставить компьютер делать все то, что вам делать лень.
Для "спасибо" есть кнопка "Спасибо" в виде звездочки внизу под ником автора поста.

Аватара пользователя
Naeel Maqsudov
Сообщения: 2551
Зарегистрирован: 20 фев 2004, 19:17
Откуда: Moscow, Russia
Контактная информация:

Re: двойная рекурсия

Сообщение Naeel Maqsudov » 09 июл 2013, 14:13

Если с одинарной понятно, то какие проблемы? Когда произойдёт возврат из первого d(n-1), то только тогда та же самая канитель повторится еще раз. :)

Т.е. если при одинарном рекурсивном вызове d(n-1) у нас получается вырожденное в список дерево. Такую рекурсию можно смело заменить на цикл. (Что, к слову, компиляторы некоторых языком делают самостоятельно).

А если вызывать 2 раза, то получится классический обход сбалансированного бинарного дерева
d(2),d(1),d(0),d(0),d(1),d(0),d(0),d(2),d(1),d(0),d(0),d(1),d(0),d(0)

Ответить