Составители:
Рубрика:
3
Лабораторная работа N8.
Использование рекурсивных вызовов в программах на языке
Си.
Цель работы:
Познакомиться с одним из эффективных способов решения сложных
задач – рекурсией. Приобрести навыки программирования с ее
использованием.
Общие сведения:
Очень часто, разрабатывая программу, удается свести исходную
задачу к более простым. Среди этих задач может оказаться и
первоначальная, но в упрощенной форме. Например, вычисление функции
F(n) может потребовать вычисления F(n-1) и еще каких-то операций.
Иными словами, частью алгоритма вычисления функции будет
вычисление этой же функции.
Алгоритм называется рекурсивным, если он прямо или косвенно
обращается к самому себе. Часто в основе такого алгоритма лежит
рекурсивное определение какого-то понятия. Например, о факториале
числа N можно сказать, что N! = N*(N – 1)!, если N > 0 и N! = 1 если N = 0.
Это – рекурсивное определение.
Любое рекурсивное определение состоит из двух частей. Эти части
принято называть базовой и рекурсивной частями. Базовая часть является
нерекурсивной и задает определение для некоторой фиксированной части
объектов. Рекурсивная часть определяет понятие через него же и
записывается так, чтобы при цепочке повторных применений она
редуцировалась бы к базе.
Всякая функция в языке Си имеет реентерабельный (повторно вхо-
димый) код, что позволяет ей обращаться к самой себе непосредственно
или через другие функции. Такие обращения называются рекурсивными
вызовами или рекурсией.
При каждом очередном рекурсивном вызове в специальной области
памяти программы, называемой стеком, создается новая копия
параметров функции, а также определенных в ее теле автоматических и
регистровых переменных. Внешние и статические переменные, имеющие
глобальное время существования, сохраняют при этом свои прежние зна-
чения и размещение памяти.
Несмотря на то, что стандарт языка Си, формально не налагают
никакого ограничения на количество рекурсивных обращений, тем не
менее, оно практически всегда существует для любых типов ЭВМ, так
как каждый новый вызов требует дополнительной памяти из ресурса
программного стека. Если количество вызовов (глубина рекурсии)
излишне велико, возникает переполнение сегмента стека и операционная
Лабораторная работа N8.
Использование рекурсивных вызовов в программах на языке
Си.
Цель работы:
Познакомиться с одним из эффективных способов решения сложных
задач – рекурсией. Приобрести навыки программирования с ее
использованием.
Общие сведения:
Очень часто, разрабатывая программу, удается свести исходную
задачу к более простым. Среди этих задач может оказаться и
первоначальная, но в упрощенной форме. Например, вычисление функции
F(n) может потребовать вычисления F(n-1) и еще каких-то операций.
Иными словами, частью алгоритма вычисления функции будет
вычисление этой же функции.
Алгоритм называется рекурсивным, если он прямо или косвенно
обращается к самому себе. Часто в основе такого алгоритма лежит
рекурсивное определение какого-то понятия. Например, о факториале
числа N можно сказать, что N! = N*(N – 1)!, если N > 0 и N! = 1 если N = 0.
Это – рекурсивное определение.
Любое рекурсивное определение состоит из двух частей. Эти части
принято называть базовой и рекурсивной частями. Базовая часть является
нерекурсивной и задает определение для некоторой фиксированной части
объектов. Рекурсивная часть определяет понятие через него же и
записывается так, чтобы при цепочке повторных применений она
редуцировалась бы к базе.
Всякая функция в языке Си имеет реентерабельный (повторно вхо-
димый) код, что позволяет ей обращаться к самой себе непосредственно
или через другие функции. Такие обращения называются рекурсивными
вызовами или рекурсией.
При каждом очередном рекурсивном вызове в специальной области
памяти программы, называемой стеком, создается новая копия
параметров функции, а также определенных в ее теле автоматических и
регистровых переменных. Внешние и статические переменные, имеющие
глобальное время существования, сохраняют при этом свои прежние зна-
чения и размещение памяти.
Несмотря на то, что стандарт языка Си, формально не налагают
никакого ограничения на количество рекурсивных обращений, тем не
менее, оно практически всегда существует для любых типов ЭВМ, так
как каждый новый вызов требует дополнительной памяти из ресурса
программного стека. Если количество вызовов (глубина рекурсии)
излишне велико, возникает переполнение сегмента стека и операционная
3
