Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Рекурсия(Явная и неявная)
|
|
Если в теле функции явно используется вызов той же самой функции, то имеет место прямая(явная) рекурсия (self-calling), как в приведенных примерах. Если две или более функций взаимно вызывают друг друга, то имеет место косвенная(неявная) рекурсия.
В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Реализация рекурсии:
Вызов рекурсивной функции должен выполняться по условию
Последовательный вызов функцией самой себя называют рекурсивным спуском, последовательный выход из многократного вызова — рекурсивным подъёмом.
При каждом рекурсивном вызове функции заново выделяется память под локальные переменные.
Примеры рекурсии:
Рекурсивная функция вычисления факториала (прямая рекурсия)
long Fact(int k)
{ if (k==0) return 1;
return (k*Fact(k-1)); // рекурсивный вызов!
}
1)Прямая рекурсия функции main() на языке C++:
#include < iostream>
using namespace std;
int main()
{
cout < < " Hello world! " < < endl;
main();
return 0;
}
2)Косвенная рекурсия функции main() на языке C++:
#include < iostream>
using namespace std;
void f();
int main()
{
cout < < " Hello world! " < < endl;
f();
return 0;
}
void f()
{
main();
}
В обоих примерах на экране монитора достаточно долго будет выводится радостный текст
Hello world!
а затем произойдёт аварийное завершение программы из-за переполнения стека.
Сортировка Хоара (Итеративный вариант)
#define MAXSTACK 2048 // максимальный размер стека
template< class T>
void qSortI(T a[], long size) {
long i, j; // указатели, участвующие в разделении
long lb, ub; // границы сортируемого в цикле фрагмента
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Зарегистрироваться и Начать продвижение
long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
// каждый запрос задается парой значений,
// а именно: левой(lbstack) и правой(ubstack)
// границами промежутка
long stackpos = 1; // текущая позиция стека
long ppos; // середина массива
T pivot; // опорный элемент
T temp;
lbstack[1] = 0;
ubstack[1] = size-1;
do {
// Взять границы lb и ub текущего массива из стека.
lb = lbstack[ stackpos ];
ub = ubstack[ stackpos ];
stackpos--;
do {
// Шаг 1. Разделение по элементу pivot
ppos = (lb + ub) > > 1;
i = lb; j = ub; pivot = a[ppos];
do {
while (a[i] < pivot) i++;
while (pivot < a[j]) j--;
if (i < = j) {
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
}
} while (i < = j);
// Сейчас указатель i указывает на начало правого подмассива,
// j - на конец левого (см. иллюстрацию выше), lb? j? i? ub.
// Возможен случай, когда указатель i или j выходит за границу массива
// Шаги 2, 3. Отправляем большую часть в стек и двигаем lb, ub
if (i < ppos) { // правая часть больше
if (i < ub) { // если в ней больше 1 элемента - нужно
stackpos++; // сортировать, запрос в стек
lbstack[ stackpos ] = i;
ubstack[ stackpos ] = ub;
}
ub = j; // следующая итерация разделения
// будет работать с левой частью
} else { // левая часть больше
if (j > lb) {
stackpos++;
lbstack[ stackpos ] = lb;
ubstack[ stackpos ] = j;
}
lb = i;
}
} while (lb < ub); // пока в меньшей части более 1 элемента
} while (stackpos! = 0); // пока есть запросы в стеке
}
Сортировка Хоара (рекурсивный вариант)
template< class T>
void quickSortR(T* a, long N) {
// На входе - массив a[], a[N] - его последний элемент.
long i = 0, j = N; // поставить указатели на исходные места
T temp, p;
p = a[ N> > 1 ]; // центральный элемент
// процедура разделения
do {
while (a[i] < p) i++;
while (a[j] > p) j--;
if (i < = j) {
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
}
} while (i< =j);
// рекурсивные вызовы, если есть, что сортировать
if (j > 0) quickSortR(a, j);
if (N > i) quickSortR(a+i, N-i);
}
Ханойские башни:
Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
#include < stdio.h>
#include < conio.h>
— Разгрузит мастера, специалиста или компанию;
— Позволит гибко управлять расписанием и загрузкой;
— Разошлет оповещения о новых услугах или акциях;
— Позволит принять оплату на карту/кошелек/счет;
— Позволит записываться на групповые и персональные посещения;
— Поможет получить от клиента отзывы о визите к вам;
— Включает в себя сервис чаевых.
Для новых пользователей первый месяц бесплатно. Зарегистрироваться в сервисе
char a, b, c;
int num;
void hanoy(int num, char a, char b, char c){
if(num> 0)
{
hanoy(num-1, a, c, b);
printf(" %c---> %c\n", a, c);
hanoy(num-1, b, a, c);
}
}
void main(){
printf(" number of rings=");
scanf(" %d", & num);
a='A'; b='B'; c='C';
hanoy(num, a, b, c);
}
|
|