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

Обновлено: 06.07.2024

Простейший пример рекуррентного соотношения: F(0)=1, F(1)=1*F(0), F(2)=2*F(1), … , F(n)=n*F(n-1). Как Вы понимаете, это вычисление факториала. Но можно эти соотношения записать короче: F(n)=n*F(n-1) для n=1,2,…,N, причем F(0)=1.

Рекуррентные соотношения могут быть реализованы как через цикл (от начала к концу), так и через рекурсию (от конца к началу). Часто используют такие структуры данных, для которых целесообразно применять рекурсивные методы при написании программ.

Рекурсивные методы удобны при работе с рекурсивными структурами данных — списками, деревьями.

Примеры применения рекурсивных методов: вычисление факториала, Ханойские башни, закрашивание замкнутой области (см. ниже), подсчет числа слов в тексте, поиск пути в лабиринте, обход деревьев, обработка списков.

Необходимые определения

Метод P называется рекурсивным, если при выполнении тела метода происходит вызов метода P.
Рекурсия может быть прямой, если вызов P происходит непосредственно в теле метода P.
Рекурсия может быть косвенной, если в теле P вызывается метод Q (эта цепочка может быть продолжена), в теле которого вызывается метод P.
Важно! Для того чтобы рекурсия не приводила к зацикливанию, в тело нормального рекурсивного метода всегда встраивается оператор выбора, одна из ветвей которого не содержит рекурсивных вызовов.

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

Приведем традиционный пример рекурсивного определения функции, вычисляющей

Факториал целого числа

Минимальное число операций равно 2 n -1. Попробуйте придумать более быстрый алгоритм, не изменяя условия задачи. При n=30 мы имеем более 1 миллиарда операций.

А вот практический пример применения рекурсии —

Закрашивание замкнутой области

Основная идея рекурсии заложена в func(char[][] b, int x, int y): проверка соседних клеток на предмет возможности закрашивания произвольной замкнутой области.

Пример косвенной рекурсии

Через рекуррентные соотношения, используя цикл, найти C_N и S_N.
Записать решение, используя косвенную рекурсию.
Сравнить время выполнения алгоритмов для N = 10, 11, … , 32.

Решение

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

Завершим раздел рассмотрением двух из трех ключевых принципов ООП — наследования и полиморфизма, считаю принцип инкапсуляции уже достаточно ясным.

В этой статье речь пойдет о задачах на рекурсию и о том как их решать.

Кратко о рекурсии

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

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

Задачи

При изучении рекурсии наиболее эффективным для понимания рекурсии является решение задач.

Как же решать задачи на рекурсию ?

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

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

Для обоснования можно привести такие доводы.

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

После чего можно сделать вывод, что они взаимно заменимы, но не всегда с одинаковыми затратами по ресурсам и скорости. Для обоснования можно привести такой пример: имеется функция, в которой для организации некого алгоритма имеется цикл, выполняющий последовательность действий в зависимости от текущего значения счетчика (может от него и не зависеть). Раз имеется цикл, значит, в теле повторяется последовательность действий — итерации цикла. Можно вынести операции в отдельную подпрограмму и передавать ей значение счетчика, если таковое есть. По завершению выполнения подпрограммы мы проверяем условия выполнения цикла, и если оно верно, переходим к новому вызову подпрограммы, если ложно — завершаем выполнение. Т.к. все содержание цикла мы поместили в подпрограмму, значит, условие на выполнение цикла помещено также в подпрограмму, и получить его можно через возвращающее значение функции, параметры передающееся по ссылке или указателю в подпрограмму, а также глобальные переменные. Далее легко показать, что вызов данной подпрограммы из цикла легко переделать на вызов, или не вызов (возврата значения или просто завершения работы) подпрограммы из нее самой, руководствуясь какими-либо условиями (теми, что раньше были в условии цикла). Теперь, если посмотреть на нашу абстрактную программу, она примерно выглядит как передача значений подпрограмме и их использование, которые изменит подпрограмма по завершению, т.е. мы заменили итеративный цикл на рекурсивный вызов подпрограммы для решения данного алгоритма.

Задача по приведению рекурсии к итеративному подходу симметрична.

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

Более подробно с этим можно познакомиться тут

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

Условие остановки или же Базовый случай
Условие продолжения или Шаг рекурсии — способ сведения задачи к более простым.

Тут Базовым условием является условие когда n=1. Так как мы знаем что 1!=1 и для вычисления 1! нам ни чего не нужно. Чтобы вычислить 2! мы можем использовать 1!, т.е. 2!=1!*2. Чтобы вычислить 3! нам нужно 2!*3… Чтобы вычислить n! нам нужно (n-1)!*n. Это и является шагом рекурсии. Иными словами, чтобы получить значение факториала от числа n, достаточно умножить на n значение факториала от предыдущего числа.

В сети при обьяснении рекурсии также даются задачи нахождения чисел Фибоначчи и Ханойская башня

Рассмотрим же теперь задачи с различным уровнем сложности.
Попробуйте их решить самостоятельно используя метод описанный выше. При решении попробуйте думать рекурсивно. Какой базовый случай в задаче? Какой Шаг рекурсии или рекурсивное условие?

Поехали! Решения задач предоставлены на языке Java.

A: От 1 до n
Дано натуральное число n. Выведите все числа от 1 до n.

B: От A до B
Даны два целых числа A и В (каждое в отдельной строке). Выведите все числа от A до B включительно, в порядке возрастания, если A 1. Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число составное. Алгоритм должен иметь сложность O(logn).
Указание. Понятно, что задача сама по себе нерекурсивна, т.к. проверка числа n на простоту никак не сводится к проверке на простоту меньших чисел. Поэтому нужно сделать еще один параметр рекурсии: делитель числа, и именно по этому параметру и делать рекурсию.

I: Разложение на множители
Дано натуральное число n>1. Выведите все простые множители этого числа в порядке неубывания с учетом кратности. Алгоритм должен иметь сложность O(logn).

J: Палиндром
Дано слово, состоящее только из строчных латинских букв. Проверьте, является ли это слово палиндромом. Выведите YES или NO.
При решении этой задачи нельзя пользоваться циклами, в решениях на питоне нельзя использовать срезы с шагом, отличным от 1.

K: Вывести нечетные числа последовательности
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Выведите все нечетные числа из этой последовательности, сохраняя их порядок.
В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция не возвращает значение, а сразу же выводит результат на экран. Основная программа должна состоять только из вызова этой функции.

L: Вывести члены последовательности с нечетными номерами
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Выведите первое, третье, пятое и т.д. из введенных чисел. Завершающий ноль выводить не надо.
В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция не возвращает значение, а сразу же выводит результат на экран. Основная программа должна состоять только из вызова этой функции.

M: Максимум последовательности
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите наибольшее значение числа в этой последовательности.
В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция возвращает единственное значение: максимум считанной последовательности. Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля).

N: Среднее значение последовательности
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите среднее значение элементов этой последовательности (без учета последнего нуля).
В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает кортеж из пары чисел: число элементов в последовательности и их сумма. В программе на языке C++ результат записывается в две переменные, которые передаются в функцию по ссылке.
Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля).

O: Второй максимум
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите значение второго по величине элемента в этой последовательности, то есть элемента, который будет наибольшим, если из последовательности удалить наибольший элемент.
В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает результат в виде кортежа из нескольких чисел и функция вообще не получает никаких параметров. В программе на языке C++ результат записывается в переменные, которые передаются в функцию по ссылке. Других параметров, кроме как используемых для возврата значения, функция не получает.
Гарантируется, что последовательность содержит хотя бы два числа (кроме нуля).

P: Количество элементов, равных максимуму
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите, какое количество элементов этой последовательности, равны ее наибольшему элементу.
В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает результат в виде кортежа из нескольких чисел и функция вообще не получает никаких параметров. В программе на языке C++ результат записывается в переменные, которые передаются в функцию по ссылке. Других параметров, кроме как используемых для возврата значения, функция не получает.
Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля).

Q: Количество единиц
Дана последовательность натуральных чисел (одно число в строке), завершающаяся двумя числами 0 подряд. Определите, сколько раз в этой последовательности встречается число 1. Числа, идущие после двух нулей, необходимо игнорировать.
В этой задаче нельзя использовать глобальные переменные и параметры, передаваемые в функцию. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметров.

R: Треугольная последовательность
Дана монотонная последовательность, в которой каждое натуральное число k встречается ровно k раз: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4,…
По данному натуральному n выведите первые n членов этой последовательности. Попробуйте обойтись только одним циклом for.

S: Заданная сумма цифр
Даны натуральные числа k и s. Определите, сколько существует k-значных натуральных чисел, сумма цифр которых равна d. Запись натурального числа не может начинаться с цифры 0.
В этой задаче можно использовать цикл для перебора всех цифр, стоящих на какой-либо позиции.

T: Без двух нулей
Даны числа a и b. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом.

U: Разворот числа
Дано число n, десятичная запись которого не содержит нулей. Получите число, записанное теми же цифрами, но в противоположном порядке.
При решении этой задачи нельзя использовать циклы, строки, списки, массивы, разрешается только рекурсия и целочисленная арифметика.
Фунция должна возвращать целое число, являющееся результатом работы программы, выводить число по одной цифре нельзя.
Update от Eivind

Вот и все. Надеюсь решение задач принесло вам столько же удовольствия сколько и мне!

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

Чтобы понять рекурсию нужно понять рекурсию.

Рекурсия — вызов функции из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A.

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

Например, для вычисления F(N) может понадобиться вычислить F(N−1). Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции.

Итак, функция является рекурсивной, если она обращается сама к себе прямо или косвенно (через другие функции). Заметим, что при косвенном обращении все функции в цепочке – рекурсивные.

Рассмотрим это на примере функции вычисления факториала. Хорошо известно, что \(0!=1\), \(1!=1\). А как вычислить величину \(n!\) для бОльших \(n\)? Если бы мы могли вычислить величину \((n−1)!\), то тогда мы легко вычислили бы \(n!\), поскольку \(n!=n\cdot(n−1)!\). Но как вычислить \((n−1)!\)? Если бы мы вычислили \((n−2)!\), то мы сможем вычисли и \((n−1)! = (n−1)\cdot(n−2)!\). А как вычислить \((n−2)!\)? Если бы. В конце концов, мы дойдем до величины \(0!\), которая равна \(1\). Таким образом, для вычисления факториала мы можем использовать значение факториала для меньшего числа. Это можно сделать и в программе на Си:

Краткая формулировка обоснования рекурсивного алгоритма вычисления факториала:

если N = 0, то N! = 1

Как это работает?

Допустим, мы вызвали функцию factorial(4). Будет вызвана функция, у которой значение параметра n равно 4. Она проверит условие n == 0, поскольку условие ложно, то будет выполнена инструкция return n * factorial(n - 1). Но чтобы вычислить это значение, будет вызвана функция factorial(3), так как параметр n имеет значение, равное 4. Теперь в памяти будет находиться две функции factorial -- одна со значением параметра n равным 4, а другая — со значением 3. При этом активна будет последняя функция.

Эта функция в свою очередь вызовет функцию factorial(2), та вызовет функцию factorial(1), затем factorial(0). В случае этой функции ничего более вызвано не будет, функция просто вернет значение 1, и управление вернется в функцию factorial(1). Та умножит значение n = 1 на значение 1, которое вернула функция factorial(0), и вернет полученное произведение, равное 1. Управление вернется в функцию factorial(2), которая умножит n = 2 на значение 1, которое вернула функция factorial(1) и вернет полученное произведение, равное 2. Функция factorial(3) вернет \(3\times2 = 6\), а функция factorial(4) вернет \(4 \times 6 == 24\).

Таблица последовательности вызовов функции приведена ниже. Значения функции возвращают в порядке, обратном порядку их вызова, то есть сначала заканчивает работу функция factorial(0), затем factorial(1) и т. д.

С какими параметрами вызвана функция	Какое значение вернула
factorial(4)	4 * 6 = 24
factorial(3)	3 * 2 = 6
factorial(2)	2 * 1 = 2
factorial(1)	1 * 1 = 1
factorial(0)	1

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

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

Какой случай (для какого набора параметров) будет крайним (простым) и что функция возвращает в этом случае?
Как свести задачу для какого-то набора параметров (за исключением крайнего случая) к задаче, для другого набора параметров (как правило, с меньшими значениями)?

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

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

Рекурсия изнутри

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

в памяти размещаются параметры, передаваемые функции (но не параметры-переменные, т. к. они передаются по ссылке!);
для внутренних переменных вызываемой функции также отводится новая область памяти (несмотря на совпадение их имен и типов с переменными вызывающей функции);
запоминается адрес возврата в вызывающую функцию;
управление передается вызванной функции.

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

В этом руководстве мы узнаем о рекурсивной функции в C++ и ее работе с помощью примеров.
Функция, которая вызывает сама себя, называется рекурсивной функцией. И этот метод известен как рекурсия.

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

На рисунке ниже показано, как работает рекурсия, вызывая себя снова и снова.

Рекурсия продолжается до тех пор, пока не будет выполнено какое-либо условие.

Чтобы предотвратить бесконечную рекурсию, можно использовать оператор if … else (или аналогичный подход), когда одна ветвь выполняет рекурсивный вызов, а другая – нет.

Пример 1: факториал числа с использованием рекурсии

Работа программы

Как мы видим, функция factorial() вызывает саму себя. Однако во время каждого вызова мы уменьшали значение n на 1. Когда n меньше 1, функция factorial() в конечном итоге возвращает результат.

Читайте также: