Как работает рекурсия в си

Как работает рекурсия в си

Отдельно остановимся на рекурсивных функциях. Рекурсивная функция представляет такую конструкцию, при которой функция вызывает саму себя.

Рекурсивная функция факториала

Возьмем, к примеру, вычисление факториала, которое использует формулу n! = 1 * 2 * … * n . То есть по сути для нахождения факториала числа мы перемножаем все числа до этого числа. Например, факториал числа 4 равен 24 = 1 * 2 * 3 * 4 , а факторил числа 5 равен 120 = 1 * 2 * 3 * 4 * 5 .

Определим метод для нахождения факториала:

При создании рекурсивной функции в ней обязательно должен быть некоторый базовый вариант , с которого начинается вычисление функции. В случае с факториалом это факториал числа 1, который равен 1. Факториалы всех остальных положительных чисел будет начинаться с вычисления факториала числа 1, который равен 1.

На уровне языка программирования для возвращения базового варианта применяется оператор return :

То есть, если вводимое число равно 1, то возвращается 1

Другая особенность рекурсивных функций: все рекурсивные вызовы должны обращаться к подфункциям, которые в конце концов сходятся к базовому варианту:

Так, при передаче в функцию числа, которое не равно 1, при дальнейших рекурсивных вызовах подфункций в них будет передаваться каждый раз число, меньшее на единицу. И в конце концов мы дойдем до ситуации, когда число будет равно 1, и будет использован базовый вариант. Это так называемый рекурсивный спуск.

Используем эту функцию:

Рассмотрим поэтапно, что будет в случае вызова factorial(4) .

Сначала идет проверка, равно ли число единице:

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

То есть фактически мы имеем:

Далее выполняется выражение:

Опять же n не равно 1, поэтому выполняется код

То есть фактически:

Далее выполняется выражение:

Опять же n не равно 1, поэтому выполняется код

То есть фактически:

Далее выполняется выражение:

Теперь n равно 1, поэтому выполняется код

И возвращается 1.

В итоге выражение

В реальности выливается в

Рекурсивная функция Фибоначчи

Другим распространенным показательным примером рекурсивной функции служит функция, вычисляющая числа Фибоначчи. n-й член последовательности Фибоначчи определяется по формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1. То есть последовательность Фибоначчи будет выглядеть так 0 (0-й член), 1 (1-й член), 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . Для определения чисел этой последовательности определим следующий метод:

Здесь базовый вариант выглядит следующий образом:

То есть, если мы ищем нулевой или первый элемент последовательности, то возвращается это же число — 0 или 1. Иначе возвращается результат выражения fibonachi(n — 1) + fibonachi(n — 2);

Рекурсии и циклы

Это простейшие пример рекурсивных функций, которые призваны дать понимание работы рекурсии. В то же время для обоих функций вместо рекурсий можно использовать циклические конструкции. И, как правило, альтернативы на основе циклов работают быстрее и более эффективны, чем рекурсия. Например, вычисление чисел Фибоначчи с помощью циклов:

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

57. Рекурсия в языке Си.

В языке Си функции могут вызывать сами себя, т.е. обладать свойством рекурсивности. Рекурсивная функция обязательно должна содержать в себе условие окончания рекурсивности, чтобы не вызвать зацикливания программы. При каждом рекурсивном вызове создается новое мно­жество локальных переменных. Т.о. переменные, расположенные вне вызываемой функции, не изменяются.

Пример. Составить рекурсивную функцию, вычисляющую факториал числа n следующим образом: n!= 1 , если n<= 1 и n!= ( n -1 )! · n, если n > 1

long fact( int n)

else return (n * fact ( n -1 )); // функция fact вызывает саму себя

Таким образом, последовательно вызываются функции f(n), f(n-1),f(n-2)…f(1).

Достоинством рекурсий является компактная запись, а недостатком – расход времени и памяти на повторные вызовы функции и передачу ей копий параметров.

58. Указатель на функцию в языке Си.

Возможны только две операции с функциями: вызов и взятие адреса. Указатель, полученный с помощью последней операции, можно впоследствии использовать для вызова функции. Например:

Для вызова функции с помощью указателя (efct в нашем примере) надо вначале применить операцию косвенности к указателю — *efct. Поскольку приоритет операции вызова () выше, чем приоритет косвенности *, нельзя писать просто *efct(«error»). Это будет означать *(efct(«error»)), что является ошибкой. По той же причине скобки нужны и при описании указателя на функцию. Однако, писать просто efct(«error») можно, т.к. транслятор понимает, что efct является указателем на функцию, и создает команды, делающие вызов нужной функции.

Отметим, что формальные параметры в указателях на функцию описываются так же, как и в обычных функциях. При присваивании указателю на функцию требуется точное соответствие типа функции и типа присваиваемого значения.

59. Классы хранения переменных языка Си.

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

В языке C имеется 4 класса памяти:

— extern (внешние переменные);

— auto (автоматические переменные);

— register (регистровые переменные);

— static (статические переменные);

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

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

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

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

Служебное слово, определяющее класс памяти, ставится в описаниях переменных перед служебным словом, задающим тип переменных:

Рекурсия

Рекурсия — состоит в определении, описании, изображении какого-либо объекта или процесса внутри самого этого объекта или процесса. Это ситуация, когда объект является частью самого себя.

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

Процедура func() вызывается с параметром 3. В ней содержится вызов процедуры func() с параметром 2. Предыдущий вызов еще не завершился, поэтому создается еще одна процедура и до окончания ее работы func(3) свою работу приостанавливает. Процесс вызова заканчивается, когда параметр равен 0. В этот момент одновременно выполняются 4 экземпляра процедуры.

Количество одновременно выполняемых процедур называют глубиной рекурсии .

Последняя вызванная процедура func(0) выведет число 0 и закончит свою работу. После этого управление возвращается к процедуре, которая ее вызвала: func(1) и выводится число 1. И так далее пока не завершатся все процедуры.

Важным и обязательным моментом в формировании рекурсивной процедуры является базис рекурсии. Базис рекурсии определяет условие выхода из рекурсии. Как правило, в качестве базиса записывается некий простейший случай, при котором ответ получается сразу, без использования рекурсии.
Существует такое понятие как шаг рекурсии или рекурсивный вызов . В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение.

Сложная рекурсия

Возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называется сложной рекурсией . При этом оказывается, что описываемая первой процедура должна вызывать еще не описанную. Чтобы это было возможно, требуется использовать описание функции B до ее использования.
Пример : вычислить значение выражения

Результат выполнения

Префиксная и постфиксная форма записи

Если процедура вызывает сама себя, то, по сути, это приводит к повторному выполнению содержащихся в ней инструкций, что аналогично работе цикла. При этом различают префиксную и постфиксную формы записи.

Как работает рекурсия в си

Функция называется рекурсивной, если во время ее обработки возникает ее повторный вызов, либо непосредственно, либо косвенно, путем цепочки вызовов других функций.

Прямой (непосредственной) рекурсией является вызов функции внутри тела этой функции.

Косвенной рекурсией является рекурсия, осуществляющая рекурсивный вызов функции посредством цепочки вызова других функций. Все функции, входящие в цепочку, тоже считаются рекурсивными.

Все функции a,b,c являются рекурсивными, так как при вызове одной из них, осуществляется вызов других и самой себя.

Рассмотрим задачу о Ханойских башнях. Имеются три стержня с номерами 1,2,3. На стержень 1 надето n дисков различного диаметра так, что они образуют пирамиду (см.рис.31). Написать программу для печати последовательности перемещений дисков со стержня на стержень, необходимых для переноса пирамиды со стержня 1 на стержень 3 при использовании стержня 2 в качестве вспомогательного. При этом за одно перемещение должен переноситься только один диск, и диск большего диаметра не должен помещаться на диск меньшего диаметра. Доказано, что для n дисков минимальное число необходимых перемещений равно 2^n-1.

Рис.31. Задача о Ханойских башнях.

Для решения простейшего случая задачи, когда пирамида состоит только из одного диска, необходимо выполнить одно действие — перенести диск со стержня i на стержень j, что очевидно (этот перенос обозначается i -> j). Общий случай задачи изображен на рисунке, когда требуется перенести n дисков со стержня i на стержень j, считая стержень w вспомогательным. Сначала следует перенести n-1 диск со стержня i на стержень w при вспомогательном стержне j, затем перенести один диск со стержня i на стержень j и, наконец, перенести n-1 диск из w на стержень j, используя вспомогательный стержень i. Итак, задача о переносе n дисков сводится к двум задачам о переносе n-1 диска и одной простейшей задаче. Схематически это можно записать так: T(n,i,j,w) = T(n-1,i,w,j), T(1,i,j,w), T(n-1,w,j,i).

Ниже приведена программа, которая вводит число n и печатает список перемещений, решающая задачу о Ханойских башнях при количестве дисков n. Используется внутренняя рекурсивная процедура tn(n,i,j,w), печатающая перемещения, необходимые для переноса n дисков со стержня i на стержень j с использованием вспомогательного стержня w при = <1,3,2>.

Последовательность вызовов процедуры tn при m=3 иллюстрируется древовидной структурой на рис.33. Каждый раз при вызове процедуры tn под параметры n, i, j, w выделяется память и запоминается место возврата. При возврате из процедуры tn память, выделенная под параметры n, i, j, w, освобождается и становится доступной память, выделенная под параметры n, i, j, w предыдущим вызовом, а управление передается в место возврата.

Рис.33. Последовательность вызовов процедуры tn.

Во многих случаях рекурсивные функции можно заменить на эквивалентные нерекурсивные функции или фрагменты, используя стеки для хранения точек вызова и вспомогательных переменных.

Предположим, что имеется ситуация:

Здесь в функции main вызывается рекурсивная функция f. Требуется заменить описание функции f и ее вызова на эквивалентный фрагмент программы, т.е. удалить функцию f.

Пусть рекурсивная функция f имеет параметры Р1,Р2. Рs, внутренние переменные V1,V2. Vt и в функциях main и f имеется k обращений к функции f. Для удаления такой функции требуются следующие дополнительные объекты:

— переменные AR1,AR2. ARs, содержащие значения фактических параметров при вызове функции f (типы переменных должны соответствовать типам параметров Р1,Р2. Рs);

— переменная rz для вычисляемого функцией f результата (тип переменных совпадает с типом возвращаемого значения функции f);

— стек, содержащий в себе все параметры и все внутренние переменные функции f, а также переменную lr типа int, для хранения точки возврата, и переменную pst типа указатель, для хранения адреса предыдущего элемента стека;

— указатель dl для хранения адреса вершин стека;

— промежуточный указатель u для операций над стеком;

— k новых меток L1. Lk для обозначенных точек возврата;

— метка jf, используемая для обхода модифицированного тела функции f;

— промежуточная переменная l типа int для передачи номера точки возврата.

Чтобы получить эквивалентную нерекурсивную программу без функции f, необходимо выполнить следующие действия:

1. Убрать объявление функции f в функцию main;

2. Добавить в функции main объявления переменных AR1,AR2. ARs,RZ, объявления стека ST и указателей dl и u:

3. Модифицировать тело функции f во фрагмент программы. Для этого следует:

а) удалить заголовок функции f;

б) объявления параметров и внутренних переменных и заменить фрагментом:

в) в конце функции f поставить метку JF, а все обращения к формальным аргументам заменить обращением, к соответствующим элементам стека;

г) вместо каждого оператора return(y) в функции f записать фрагмент:

4. Каждый i-тый вызов функции f (как в вызывающей функции, так и в теле функции f) вида V=f(A1,A2. As) заменить фрагментом программы :

где l=i обозначает l=1 при первом обращении к функции f, l=2 при втором обращении и т.д. Нумерация обращений может быть выполнена в произвольном порядке и требуется для возвращения в точку вызова с помощью операторов switch и goto Li; (где Li есть L1 при первой замене, Li есть L2 при второй замене и т.д.)

5. Вставить модифицированное тело функции f в конце функции main.

Для иллюстрации изложенного рассмотрим несколько вариантов реализации программы вычисляющей функцию Аккермана, которая определяется так:

Следующая программа вычисляет функцию Аккермана с использованием рекурсивной функции ackr и вспомогательной функции smacc: