Читать онлайн «Рекурсия: Методические указания по курсу ''Информатика''»
Автор Амелина Н.И.
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Федеральное государственное образовательное учреждение
высшего профессионального образования
«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
Н. И. АМЕЛИНА, А. А. ЧЕКУЛАЕВА
РЕКУРСИЯ
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
по курсу
«ИНФОРМАТИКА»
для студентов 1 курса дневного и вечернего отделений
факультета математики, механики и компьютерных наук
Ростов-на-Дону
2008
3
Методические указания разработаны сотрудниками кафедры прикладной
математики и программирования старшим преподавателем Н. И. Амелиной и
старшим преподавателем А. А. Чекулаевой. Печатается в соответствии с решением кафедры прикладной математики и
программирования факультета математики, механики и компьютерных наук
ЮФУ, протокол № 9 от 29 мая 2008 г.
4
СОДЕРЖАНИЕ
1 Рекурсия ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 4
1. 1 Рекурсивные описания и процессы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 4
1. 2 Косвенная рекурсия... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 5
1. 3 Сравнение рекурсии и итерации... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 6
2 Примеры рекурсивных подпрограмм ... ... ... ... ... ...
... ... ... ... ... ... ... ... ... ... ... ... 8
3 Задачи ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 28
4 Индивидуальные задания... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 34
ЛИТЕРАТУРА... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 38
5
1 РЕКУРСИЯ
Рекурсия – это способ описания объектов или вычислительных процессов
через самих себя.
1. 1 Рекурсивные описания и процессы
Многие математические функции можно описать рекурсивно:
⎧ 1, если n = 0
n != ⎨
⎩(n − 1) !⋅ n, если n > 0
⎧ 1, если n = 0
xn = ⎨ n −1
⎩x ⋅ x , если n>0
Рекурсивное программирование позволяет описать повторяющийся про-
цесс без явного использования операторов цикла, например:
function Fact(n: integer): integer;
begin
if n=0 then Fact:=1
else Fact:= Fact (n-1) * n
end;
Рекурсивное описание должно содержать хотя бы одну альтернативу, не
использующую рекурсивный вызов, то есть явное определение для некоторых
значений аргументов подпрограммы. Эта альтернатива – нерекурсивный случай –
завершает последовательность рекурсивных вызовов. В противном случае про-
цесс вычислений будет бесконечным. Другая форма рекурсии – рекурсивное обращение, когда процесс описыва-
ется через подпроцессы, один из которых идентичен основному процессу.
6
j
⎛ n i⎞ m
Например, нужно вычислить S = ∑ ⎜ ∑ x ⎟ Пусть функция Sum(n,x)
j =1 ⎝ i =1 ⎠
n
вычисляет ∑x
i =1
i
, тогда рекурсивное к ней обращение позволяет вычислить сум-
му : S := Sum (m, Sum (n,x));
Оба типа рекурсии могут присутствовать одновременно.
