Переместить этот единственный диск с A на C и остановиться

В общем случае любая рекурсивная функция включает в себя некоторое множество операторов S и один или несколько операторов рекурсивного вызова.

Безусловные рекурсивные функции приводят к бесконечным процессам, так как практическое использование функций с бесконечным самовызовом невозможно.
Такая невозможность вытекает из того, что для каждой копии рекурсивной функции необходимо выделять дополнительную область памяти, а бесконечной памяти не существует.

Следовательно, главное требование к рекурсивным функциям заключается в том, что вызов рекурсивной функции должен выполняться по условию, которое на каком-то уровне рекурсии станет ложным. Если условие истинно, то рекурсивный спуск продолжается. Когда оно станет ложным, спуск заканчивается и начинается поочередный рекурсивный возврат из всех вызванных на данный момент копий рекурсивной функции.

В примере выполнения рекурсивной процедуры ввода чисел и вывода их в обратном порядке, действия выполняются до рекурсивного вызова, т.е. на рекурсивном спуске (оператор scanf) и на рекурсивном возврате (оператор prinf).

Пример. Вычисление наибольшего общего делителя двух натуральных чисел.
Алгоритм Евклида реализован в виде рекурсивной функции.
int f_nod(int x, int y)
//рекурсивная функция
{
if (y>x)
return f_nod(y,x);
else
if (y==0)
return x;
else
return f_nod(y,x%y);
}

Примеры конечного рекурсивного алгоритма, определяющего бесконечные вычисления.

void Pech()
{ puts(”Отыщи всему начало”);
puts(”И ты многое поймешь! ”);
Pech();
}

void PechNO()
{ PechNO();
puts(”Отыщи всему начало”);
puts(”И ты многое поймешь! ”);
}

Задача о Ханойских башнях

Даны три стержня A, B, C. На стержне A находятся n дисков разного диаметра, пронумерованных сверху вниз. Каждый меньший диск находится на большем. Требуется переместить эти диски на стержень C, сохранив их взаиморасположение. Перемещать можно только по одному верхнему диску и нельзя класть больший диск на меньший.

**/*Алгоритм Задачи о Ханойских башнях:

Если n=1 то**

<== предыдущая лекция | следующая лекция ==>

Стандартные метрические форматы бумаги | Переместить n-1 дисков с В на С, используя А как вспомогательный
Поделиться с друзьями:

Дата добавления: 2013-12-13; Просмотров: 259; Нарушение авторских прав?; Мы поможем в написании вашей работы!
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

studopediasu.com - Студопедия (2013 - 2026) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление

Генерация страницы за: 0.008 сек.

Переместить этот единственный диск с A на C и остановиться

void Pech() { puts(”Отыщи всему начало”); puts(”И ты многое поймешь! ”); Pech(); } void PechNO() { PechNO(); puts(”Отыщи всему начало”); puts(”И ты многое поймешь! ”); }

void Pech()
{ puts(”Отыщи всему начало”);
puts(”И ты многое поймешь! ”);
Pech();
}

void PechNO()
{ PechNO();
puts(”Отыщи всему начало”);
puts(”И ты многое поймешь! ”);
}