Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Пример 3. Пример 4. Вычислить сумму элементов линейного массива.
|
|
| {Функция на 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); } } |
Задание. Используя аналогичный подход, определите, является ли заданное натуральное число палиндромом.
Подводя итог, заметим, что использование рекурсии является красивым приёмом программирования. В то же время в большинстве практических задач этот приём неэффективен с точки зрения расходования таких ресурсов ЭВМ, как память и время исполнения программы. Использование рекурсии увеличивает время исполнения программы и зачастую требует значительного объёма памяти для хранения копий подпрограммы на рекурсивном спуске. Поэтому на практике разумно заменять рекурсивные алгоритмы на итеративные.
Контрольные вопросы и задания
1. Какое определение называется рекурсивным? Приведите собственные примеры рекурсивных определений.
2. Какой вспомогательный алгоритм (подпрограмма) называются рекурсивными? Приведите собственные примеры содержательных задач, где для решения может быть использован рекурсивный вспомогательный алгоритм.
3. Что такое граничное условие, и каково его назначение в рекурсивной подпрограмме?
4. Что такое рекурсивный спуск?
5. Что такое рекурсивный подъём?
6. Что такое глубина рекурсии? Чему равна глубина рекурсии в приведённых выше примерах?
7. На каком этапе выполнения рекурсивной подпрограммы могут выполняться её операторы?
8. Почему приведённый ниже алгоритм посимвольного формирования строки завершится аварийно?
9.Function Stroka: String;
10. Var C: Char;
11. Begin
12. Write('Введите очередной символ: '); ReadLn(C);
13. Stroka: =Stroka+C
14. End;
На каком этапе выполняются действия в этом алгоритме?