Как сделать рекурсию в c

Как сделать рекурсию в c

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

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

Возьмем, к примеру, вычисление факториала, которое использует формулу 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);

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

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

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

Рекурсия в С++

Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Самый простой вариант увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.

В программировании рекурсия тесно связана с функциями, точнее именно благодаря функциям в программировании существует такое понятие как рекурсия или рекурсивная функция. Простыми словами, рекурсия – определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию). Типичными рекурсивными задачами являются задачи: нахождения n!, числа Фибоначчи. Такие задачи мы уже решали, но с использованием циклов, то есть итеративно. Вообще говоря, всё то, что решается итеративно можно решить рекурсивно, то есть с использованием рекурсивной функции. Всё решение сводится к решению основного или, как ещё его называют, базового случая. Существует такое понятие как шаг рекурсии или рекурсивный вызов. В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение. Разработаем программу, в которой объявлена рекурсивная функция, вычисляющая n!

В строках 7, 9, 21 объявлен тип данных unsigned long int , так как значение факториала возрастает очень быстро, например уже 10! = 3 628 800. Если не хватит размера типа данных, то в результате мы получим совсем не правильное значение. В коде объявлено больше операторов, чем нужно, для нахождения n!. Это сделано для того, чтобы, отработав, программа показала, что происходит на каждом шаге рекурсивных вызовов. Обратите внимание на выделенные строки кода, строки 23, 24, 28 — это рекурсивное решение n!. Строки 23, 24 являются базовым решением рекурсивной функции, то есть, как только значение в переменной f будет равно 1 или 0 (так как мы знаем, что 1! = 1 и 0! = 1), прекратятся рекурсивные вызовы, и начнут возвращаться значения, для каждого рекурсивного вызова. Когда вернётся значение для первого рекурсивного вызова, программа вернёт значение вычисляемого факториала. В строке 28 функция factorial() вызывает саму себя, но уже её аргумент на единицу меньше. Аргумент каждый раз уменьшается, чтобы достичь частного решения. Результат работы программы (см. Рисунок 1).

Рисунок 1 — Рекурсия в С++

По результату работы программы хорошо виден каждый шаг и результат на каждом шаге равен нулю, кроме последнего рекурсивного обращения. Необходимо было вычислить пять факториал. Программа сделала четыре рекурсивных обращения, на пятом обращении был найден базовый случай. И как только программа получила решение базового случая, она порешала предыдущие шаги и вывела общий результат. На рисунке 1 видно всего четыре шага потому, что на пятом шаге было найдено частное решение, что в итоге вернуло конечное решение, т. е. 120. На рисунке 2 показана схема рекурсивного вычисления 5!. В схеме хорошо видно, что первый результат возвращается, когда достигнуто частное решение, но никак не сразу, после каждого рекурсивного вызова.

Рисунок 2 — Рекурсия в С++

Итак, чтобы найти 5! нужно знать 4! и умножить его на 5; 4! = 4 * 3! и так далее. Согласно схеме, изображённой на рисунке 2, вычисление сведётся к нахождению частного случая, то есть 1!, после чего по очереди будут возвращаться значения каждому рекурсивному вызову. Последний рекурсивный вызов вернёт значение 5!.

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

В строках 16 — 19 объявлен цикл, в котором вызывается рекурсивная функция. Всё ненужное в программе закомментированно. Запустив программу, нужно ввести значение, до которого необходимо вычислить факториалы. Результат работы программы показан на рисунке 3.

Рисунок 3 — Рекурсия в С++

Теперь видно, насколько быстро возрастает факториал, кстати говоря, уже результат 14! не правильный, это и есть последствия нехватки размера типа данных. Правильное значение 14! = 87178291200.

Рассмотрим ещё одну типичную задачу — нахождение чисел Фибоначчи, используя рекурсию. Далее приведен код рекурсивного решения такой задачи. Вводим в ком строке порядковый номер числа из ряда Фибоначчи, и программа найдёт все числа из ряда Фибоначчи порядковые номера которых меньше либо равны введённого.

В строке 6 подключена библиотека <iomanip> для того, чтобы воспользоваться функцией setw() , которая в свою очередь выравнивает первый столбец чисел, то есть номера. Как мы можем заметить, сначала числа однозначные от 1 – 9, а потом идут двузначные. Если убрать данную функцию, то произойдет сдвиг влево чисел от 1 и до 9. Результат работы программы (см. Рисунок 4).

Рисунок 4 — Рекурсия в С++

Решение сводится к разбиению сложной задачи к двум более простым. Например, чтобы найти третье число из ряда Фибоначчи, необходимо сначала найти первое и второе, а потом сложить их. Первое число является частным случаем и равно 0 (нулю), второе число также является частным случаем и равно 1. Следовательно, третье число из ряда Фибоначчи равно сумме первого и второго = 1. Приблизительно так же рассуждала запрограммированная нами рекурсивная функция поиска чисел ряда Фибоначчи.

Разработаем ещё одну рекурсивную программу, решающую классическую задачу — «Ханойская башня». Даны три стержня, на одном из которых находится стопка n-го количества дисков, причём диски имеют не одинаковый размер (диски различного диаметра) и расположены таким образом, что по мере прохождения, сверху вниз по стержню диаметр дисков постепенно увеличивается. То есть диски меньшего размера должны лежать только на дисках большего размера. Необходимо переместить эту стопку дисков с начального стержня на любой другой из двух оставшихся (чаще всего это третий стержень). Один из стержней использовать как вспомогательный. Перемещать можно только по одному диску, при этом диск большего размера никогда не должен находиться над диском меньшего размера.

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

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

<Б> — стержень, на котором изначально находятся диски (базовый стержень);
<П> — вспомогательный или промежуточный стержень;
<Ф> — финальный стержень – стержень, на который необходимо переместить диски.

Далее, при описании алгоритма решения задачи будем использовать эти обозначения. Чтобы переместить три диска с <Б> на<Ф> нам необходимо сначала переместить два диска с <Б> на <П> а потом переместить третий диск(самый большой) на<Ф>, так как <Ф> свободен.

Для того, чтобы переместить n дисков с <Б> на <Ф> нам необходимо сначала переместить n-1 дисков с <Б> на <П> а потом переместить n-й диск(самый большой) на <Ф>, так как <Ф> свободен. После этого необходимо переместить n-1 дисков с <П> на <Ф>, при этом использовать стержень <Б> как вспомогательный. Эти три действия и есть весь рекурсивный алгоритм. Этот же алгоритм на псевдокоде:
n-1 переместить на <П>
n переместить на <Ф>
n-1 переместить с <П> на <Ф>, при этом использовать <Б> как вспомогательный

Рекурсия

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

Классическим примером рекурсии служит вычисление факториала числа:

Обратите внимание, что рекурсивный метод factorial вызывает сам себя, при этом переменная i с каждым вызовом уменьшается на 1.

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

Главное преимущество рекурсии заключается в том, что она позволяет реализовать некоторые алгоритмы яснее и проще, чем итерационным способом. Например, алгоритм быстрой сортировки довольно трудно реализовать итерационным способом. А некоторые задачи, например искусственного интеллекта, очевидно, требуют именно рекурсивного решения.

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

Рекурсия. Примеры рекурсивных методов (функций) в C#

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

Содержание

• 1. Что такое рекурсия? Что такое рекурсивный метод (функция)?
• 2. Как работает рекурсивный вызов метода?
• 3. Какие преимущества дает использование рекурсии в программах?
• 4. Какие недостатки использования рекурсии в программах?
• 5. Пример вычисления суммы ряда
• 6. Пример конвертирования строки «AAABCCCCAADDDEF» => «3AB4C2A3DEF»
• 7. Пример сравнения строк
• 8. Пример рекурсивной функции реверсирования строки
• 9. Пример рекурсивной функции определения, является ли строка симметричной

Поиск на других ресурсах:

1. Что такое рекурсия? Что такое рекурсивный метод (функция)?

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

Рекурсивный метод – это метод, который вызывает сам себя. В рекурсивном методе помещается вызов этого же метода по его имени.

Последовательный процесс рекурсивных вызовов метода подобен циклическому процессу.

⇑

2. Как работает рекурсивный вызов метода?

Если метод вызывает сам себя, то в памяти происходят следующие процессы:

• в системном стеке выделяется память для новых локальных переменных и параметров;
• программный код метода выполняется сначала с новыми локальными переменными и параметрами. Эти локальные переменные и параметры получают новые начальные значения. Сам программный код метода не копируется;
• при возврате из рекурсивного метода (оператор return ) происходит восстановление старых локальных переменных и параметров а также их значений в точке вызова этого метода.

⇑

3. Какие преимущества дает использование рекурсии в программах?

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

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

⇑

4. Какие недостатки использования рекурсии в программах?

В сравнении с итерационными вызовами, построение рекурсивных вызовов имеет следующие недостатки:

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

⇑

5. Пример вычисления суммы ряда

Разработать рекурсивную функцию вычисления суммы ряда

S = 5 + 10 + 15 + … + 5·n,

Программный код функции следующий

⇑

6. Пример конвертирования строки «AAABCCCCAADDDEF» => «3AB4C2A3DEF»

Данная задача очень удобно решается с помощью рекурсии. По данному образцу можно разрабатывать рекурсивные функции, которые обрабатывают строки по любым правилам.

В рекурсивной функции ConvertStr() рекурсивно просматривается вся строка. На каждом рекурсивном вызове обрабатывается один символ строки. В зависимости от позиции текущего обрабатываемого символа происходит соответствующий рекурсивный вызов функции.

Рекурсивная функция содержит следующие параметры:

• строка s типа string , которая обрабатывается;
• переменная, определяющая позицию символа в строке s на данном уровне рекурсии. Символ s[pos] имеет тип char ;
• целое число k , определяющее количество повторений символа s[pos] на данному уровне рекурсии;
• переменная c типа char , которая представляет символ на предыдущем уровне рекурсии. Это необходимо, так как символы, которые встречаются один раз подряд должны обрабатываться по особому.

Использование функции в другом программном коде

⇑

7. Пример сравнения строк

Разработать рекурсивную функцию, которая сравнивает две строки на идентичность. Две строки считаются идентичными, если:

• длина строк совпадает;
• совпадают символы каждой строки, которые находятся на одинаковых позициях.

Рекурсивная функция должна получать следующие параметры:

• ссылку на первую строку, которая сравнивается со второй строкой;
• ссылку на вторую строку, которая сравнивается с первой строкой;
• текущую позицию символов строк, которые сравниваются.

Функция должна возвращать результат типа bool . Если строки идентичны, то функция возвращает true , иначе функция возвращает false .

Использование функции в другом программном коде

⇑

8. Пример рекурсивной функции реверсирования строки

Программный код функции следующий

В функции RString() определение последнего символа в строке происходит по формуле:

Затем этот символ переводится в строку методом ToString() . Символ строки добавляется к следующему (предшествующему) символу в строке с помощью рекурсивного вызова

Поскольку функция должна что-то возвратить, то перед формулой обработки строки нужно вставить оператор return

Использование функции RString() в другом методе может быть следующим:

⇑

9. Пример рекурсивной функции определения, является ли строка симметричной

Разработать рекурсивную функцию, которая определяет есть ли симметричной часть строки s , начиная с i -го элемента и заканчивая j -м элементом

В вышеприведенной функции сравниваются символы, которые размещаются на позициях i+pos и j-pos строки с помощью оператора if

Параметр pos есть смещением, которое добавляется к значению i : i+pos . Между позициями i и j есть некоторые символы, которые формируют некоторый диапазон. Не нужно проходить параметром pos весь диапазон от i к j . Достаточно просмотреть только половину диапазона, поэтому функция содержит проверку: