Рекурсия
Функция называется рекурсивной, если во время ее обработки возникает ее повторный вызов, либо непосредственно, либо косвенно, путем цепочки вызовов других функций.
Прямой (непосредственной) рекурсией является вызов функции внутри тела этой функции.
int a() {.....a().....}
Косвенной рекурсией является рекурсия, осуществляющая рекурсивный вызов функции посредством цепочки вызова других функций. Все функции, входящие в цепочку, тоже считаются рекурсивными.
Например:
a(){.....b().....} b(){.....c().....} c(){.....a().....} .
Все функции a,b,c являются рекурсивными, так как при вызове одной из них, осуществляется вызов других и самой себя.
Рассмотрим задачу о Ханойских башнях. Имеются три стержня с номерами 1,2,3. На стержень 1 надето n дисков различного диаметра так, что они образуют пирамиду (см.рис.31). Написать программу для печати последовательности перемещений дисков со стержня на стержень, необходимых для переноса пирамиды со стержня 1 на стержень 3 при использовании стержня 2 в качестве вспомогательного. При этом за одно перемещение должен переноситься только один диск, и диск большего диаметра не должен помещаться на диск меньшего диаметра. Доказано, что для n дисков минимальное число необходимых перемещений равно 2^n-1.
Рис.31. Задача о Ханойских башнях.
Для решения простейшего случая задачи, когда пирамида состоит только из одного диска, необходимо выполнить одно действие - перенести диск со стержня i на стержень j, что очевидно (этот перенос обозначается i -> j). Общий случай задачи изображен на рисунке, когда требуется перенести n дисков со стержня i на стержень j, считая стержень w вспомогательным. Сначала следует перенести n-1 диск со стержня i на стержень w при вспомогательном стержне j, затем перенести один диск со стержня i на стержень j и, наконец, перенести n-1 диск из w на стержень j, используя вспомогательный стержень i. Итак, задача о переносе n дисков сводится к двум задачам о переносе n-1 диска и одной простейшей задаче. Схематически это можно записать так: T(n,i,j,w) = T(n-1,i,w,j), T(1,i,j,w), T(n-1,w,j,i).
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий