RECURS (516217), страница 3
Текст из файла (страница 3)
begin for i:=1 to m do write(pole[i]:2);writeln; end
else
for i:=1 to m do
begin
pole[n]:=i;
if new_r(n,pole) then ferz(n+1,m,pole);
end;
end;
begin writeln('Введите размер доски:');
readln(m);
k:=0;
ferz(1,m,pole);
end.
Процедура new_r используется для проверки уже сгенерированной комбинации (уровень n соответствует попытке установить n-го ферзя). Процедура ferz рекурсивна. На каждом уровне она может породить до m рекурсивных вызовов (в соответствии c деревом генерации вариантов). Однако общее количество рассматриваемых вариантов резко уменьшается, что можно наглядно видеть по таблице 1.
Таблица 1.
| Размер доски | Всего вариантов | Рассмотрено вариантов | Количество решений |
| 4*4 | 256 | 17 | 2 |
| 5*5 | 3125 | 54 | 10 |
| 6*6 | 46656 | 153 | 4 |
| 7*7 | 823543 | 552 | 40 |
| 8*8 | 16777216 | 2057 | 92 |
Выводы.
-
Рекурсию следует использовать тогда, когда рекурсивный алгоритм значительно проще нерекурсивного.
-
При использовании рекурсии следует обязательно проверять наличие и правильность условия выхода из рекурсии.
-
Не следует забывать о необходимости оценки размера фрейма активации и соотношения этой оценки с размером стека (с учетов развертывания рекурсии).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
