PDA

Просмотр полной версии : двойная рекурсия



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

Хыиуду
04.07.2013, 17:21
Проход по шагам (кнопка F8) вам в помощь

Naeel Maqsudov
09.07.2013, 15: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)