Рекурсивное решение: факториал числа 5

return (5*Fact(4)) 5*4*3*2

return (4*Fact(3)) 4*3*2

return (3*Fact(2)) 3*2

return (2*Fact(1)) 2*1

return (1*Fact(0)) 1*1

return (1)

Пример 2. Определим функцию K(n), которая возвращает количество цифр в заданном натуральном числе n:

int K(int N)

{

if N<10 return 1;

else return K(N div 10)+1;

}

Свойства рекурсивного решения

1.Функция вызывает саму себя

2.При каждом вызове функции решается идентичная, но меньшая задача

3.Одна из подзадач решается иначе, чем другие: в итоге одна из подзадач является базовой

4.Проверка базисных условий позволяет остановить процесс рекурсии

Ошибка в использовании рекурсии

Отсутствие базиса: void PRINT()

{ cout<<‘*’;

PRINT();

}

При вызове данной функции процесс вывода никогда не закончится, т.к. отсутствует базис

Четыре вопроса о рекурсивном решении:

Как свести задачу к идентичным задачам меньшего размера?

Как уменьшать размер задачи при каждом рекурсивном вызове

Какая задача является базовой

Можно ли достичь базиса, постоянно уменьшая размер задачи?

Числа Фибоначчи

F(n)=F(n-1)+F(n-2)

Необходимо 2 базиса:F(1)=1, F(2)=1;

int F(int n)

{ if (n<=2) return 1;

else return F(n-1)+F(n-2);

}

Цена рекурсии

Использование рекурсии может сократить размер исходного кода программы и сделать код более элегантным и понятным. Однако рекурсия имеет и свои недостатки…

Ханойские башни:

В одном из буддийских монастырей монахи уже тысячу лет занимаются перекладыванием колец. Они располагают тремя пирамидами, на которых надеты кольца разных размеров. В начальном состоянии 64 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие — кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света.

для того чтобы перенести самый большой диск, нужно сначала перенести все диски кроме последнего на второй стержень, потом перенести самый большой на третий, после чего останется перенести все остальные диски со второго на третий.

Задачу о переносе N-1 диска решается аналогично, только поменяем стержни местами (при первом переносе конечным стержнем будем считать второй, а не третий, при втором переносе начальным вместо первого будет второй).

Задача о N-1 дисков сводится к задаче о N-2

дисков, та в свою очередь к N-3 дискам, и так вплоть до 1 диска.