Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Рекурсия

Название: Рекурсия
Раздел: Рефераты по информатике, программированию
Тип: реферат Добавлен 07:00:05 28 февраля 2008 Похожие работы
Просмотров: 499 Комментариев: 4 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Рекурсия — это такой способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма (процедура или функция) в ходе выполнения ее операторов обращается сама к себе. Вообще, рекурсивным называется любой объект, который частично определяется через себя.

Например, приведенное ниже определение двоичного кода является рекурсивным:

<двоичный код> ::= <двоичная цифра> | <двоичный код><двоичная цифра>

<двоичная цифра> ::= 0 | 1

Здесь для описания понятия были использованы, так называемые, металингвистический формулы Бэкуса-Наура (язык БНФ); знак "::=" обозначает "по определению есть", знак "|" — "или".

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

Приведём другие примеры рекурсивных определений.

Пример 1. Классический пример, без которого не обходятся ни в одном рассказе о рекурсии, — определение факториала. С одной стороны, факториал определяется так: n!=1*2*3*...*n. С другой стороны, Граничным условием в данном случае является n<=1.

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

Задание. По аналогии определите функцию S(n), вычисляющую сумму цифр заданного натурального числа.

Пример 3. Функция C(m, n), где 0<=m<=n, для вычисления биномиального коэффициента по следующей формуле является рекурсивной.

Ниже будут приведены программные реализации всех этих (и не только) примеров.

Обращение к рекурсивной подпрограмме ничем не отличается от вызова любой другой подпрограммы. При этом при каждом новом рекурсивном обращении в памяти создаётся новая копия подпрограммы со всеми локальными переменными. Такие копии будут порождаться до выхода на граничное условие. Очевидно, в случае отсутствия граничного условия, неограниченный рост числа таких копий приведёт к аварийному завершению программы за счёт переполнения стека.

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

Выполнение действий в рекурсивной подпрограмме может быть организовано одним из вариантов:

Begin Begin Begin

P; операторы; операторы;

операторы; P P;

End; End; операторы

End;

рекурсивный подъём рекурсивный спуск и рекурсивный спуск, и рекурсивный подъём

Здесь P — рекурсивная подпрограмма. Как видно из рисунка, действия могут выполняться либо на одном из этапов рекурсивного обращения, либо на обоих сразу. Способ организации действий диктуется логикой разрабатываемого алгоритма.

Реализуем приведённые выше рекурсивные определения в виде функций и процедур на языке Pascal и в виде функций на языке C.

Пример 1.

{Функция на Pascal}

Function Factorial(N:integer):Extended;

Begin

If N<=1

Then Factorial:=1

Else Factorial:=Factorial(N-1)*N

End;

{Процедура на Pascal}

Procedure Factorial(N:integer; Var F:Extended);

Begin

If N<=1

Then F:=1

Else Begin Factorial(N-1, F); F:=F*N End

End;

/* Функция на C */

double Factorial(int N)

{

double F;

if (N<=1) F=1.; else F=Factorial(N-1)*N;

return F;

}

Пример 2.

{Функция на Pascal}

Function K(N:Longint):Byte;

Begin

If N<10

Then K:=1

Else K:=K(N div 10)+1

End;

{Процедура на Pascal}

Procedure K(N:Longint; Var Kol:Byte)

Begin

If N<10

Then Kol:=1

Else Begin K(N Div 10, Kol); Kol:=Kol+1 End;

End;

/* Функция на C */

int K(int N)

{ int Kol;

if (N<10) Kol=1; else Kol=K(N/10)+1;

return Kol;

}

Пример 3.

{Функция на Pascal}

function C(m, n :Byte):Longint;

Begin

If (m=0) or (m=n)

Then C:=1

Else C:=C(m, n-1)+C(m-1, n-1)

End;

{Процедура на Pascal}

Procedure C(m, n: Byte; Var R: Longint);

Var R1, R2 : Longint;

Begin

If (m=0) or (m=n)

Then R:=1

Else Begin

C(m, n-1, R1);

C(m-1, n-1, R2);

R:=R1+R2

End;

End;

/* Функция на C */

int C(int m, int n)

{ int f;

if (m==0||m==n) f=1; else f=C(m, n-1)+C(m-1, n-1);

return f;

}

Пример 4. Вычислить сумму элементов линейного массива.

При решении задачи используем следующее соображение: сумма равна нулю, если количество элементов равно нулю, и сумме всех предыдущих элементов плюс последний, если количество элементов не равно нулю.

{Программа на языке Pascal}

Program Rec2;

Type LinMas = Array[1..100] Of Integer;

Var A : LinMas;

I, N : Byte;

{Рекурсивнаяфункция}

Function Summa(N : Byte; A: LinMas) : Integer;

Begin

If N = 0 Then Summa := 0 Else Summa := A[N] + Summa(N - 1, A)

End;

{Основная программа}

Begin

Write('Количество элементов массива? '); ReadLn(N); Randomize;

For I := 1 To N Do

Begin

A[I] := -10 + Random(21); Write(A[I] : 4)

End;

WriteLn; WriteLn('Сумма: ', Summa(N, A))

End.

/* Программа на языке C */

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <time.h>

int summa(int N, int a[100]);

int i,n, a[100];

void main()

{

clrscr();

printf("\nКоличество элементов массива? "); scanf("%d", &n);

printf("\nВ сформированном массиве %d чисел:\n", n);

randomize();

for (i=0; i<n; i++)

{a[i]= -10+random(21); printf("%d ", a[i]);}

printf("Сумма: %d", summa(n-1, a));

}

int summa(int N, int a[100])

{

if (N==0) return a[0]; else return a[N]+summa(N-1, a);

}

Пример 5. Определить, является ли заданная строка палиндромом, т.е. читается одинаково слева направо и справа налево.

Идея решения заключается в просмотре строки одновременно слева направо и справа налево и сравнении соответствующих символов. Если в какой-то момент символы не совпадают, делается вывод о том, что строка не является палиндромом, если же удается достичь середины строки и при этом все соответствующие символы совпали, то строка является палиндромом. Граничное условие — строка является палиндромом, если она пустая или состоит из одного символа.

{программа на языке Pascal}

Program Palindrom;

{Рекурсивная функция}

Function Pal(S: String) : Boolean;

Begin

If Length(S)<=1

Then Pal:=True

Else Pal:= (S[1]=S[Length(S)]) and Pal(Copy(S, 2, Length(S) - 2));

End;

Var S : String;

{Основная программа}

Begin

Write('Введите строку: '); ReadLn(S);

If Pal(S) Then WriteLn('Строка является палиндромом')

Else WriteLn('Строка не является палиндромом')

End.

/* программа на языке C */

#include <stdio.h>

#include <conio.h>

#include <string.h>

char s[100];

int pal(char s[100]);

void main()

{ clrscr();

printf("\nВведитестроку: "); gets(s);

if (pal(s)) printf("Строка является палиндромом");

else printf("Строка не является палиндромом");

}

int pal(char s[100])

{ int l; char s1[100];

if (strlen(s)<=1) return 1;

else {l=s[0]==s[strlen(s)-1];

strncpy(s1, s+1, strlen(s)-2);

s1[strlen(s)-2]='\0';

return l&&pal(s1);}

}

Задание. Используя аналогичный подход, определите, является ли заданное натуральное число палиндромом.

Подводя итог, заметим, что использование рекурсии является красивым приёмом программирования. В то же время в большинстве практических задач этот приём неэффективен с точки зрения расходования таких ресурсов ЭВМ, как память и время исполнения программы. Использование рекурсии увеличивает время исполнения программы и зачастую требует значительного объёма памяти для хранения копий подпрограммы на рекурсивном спуске. Поэтому на практике разумно заменять рекурсивные алгоритмы на итеративные.

Контрольные вопросы и задания

Какое определение называется рекурсивным? Приведите собственные примеры рекурсивных определений.

Какой вспомогательный алгоритм (подпрограмма) называются рекурсивными? Приведите собственные примеры содержательных задач, где для решения может быть использован рекурсивный вспомогательный алгоритм.

Что такое граничное условие и каково его назначение в рекурсивной подпрограмме?

Что такое рекурсивный спуск?

Что такое рекурсивный подъём?

Что такое глубина рекурсии? Чему равна глубина рекурсии в приведённых выше примерах?

На каком этапе выполнения рекурсивной подпрограммы могут выполняться её операторы?

Почему приведённый ниже алгоритм посимвольного формирования строки завершится аварийно?

Function Stroka : String;

Var C : Char;

Begin

Write('Введите очередной символ: '); ReadLn(C);

Stroka:=Stroka+C

End;

На каком этапе выполняются действия в этом алгоритме?

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений22:32:31 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
15:57:08 24 ноября 2015
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
15:56:32 24 ноября 2015
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
01:10:57 24 ноября 2015

Работы, похожие на Реферат: Рекурсия

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(151013)
Комментарии (1843)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru