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

Рекурсия

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

Простым примером является функция factr(), вычисляющая факториал целого числа. Факториал числа N является произведением чисел от 1 до N. Например, факториал 3 равен 1*2*3 или 6. Как factr(), так и его итеративный эквивалент показаны ниже:

/* Вычисление факториала числа */

int factr(int n) /* рекурсивно */
int answer;
if(n==1) return(1);
answer = factr(n-1)*n;
return(answer);
>

/* Вычисление факториала числа */

int fact (int n) /* нерекурсивно */
int t, answer;
answer == 1;
for(t=1; t answer=answer*(t);
return(answer);
>

Действие нерекурсивной версии fact() должно быть совершенно очевидно. Она использует цикл, начиная с 1 и заканчивая указанным числом, последовательно перемножая каждое число на ранее полученное произведение.

Действие рекурсивной функции factr() немного более сложно. Когда factr() вызывается с аргументом 1, функция возвращает 1. В противном случае она возвращает произведение factr(n- 1) * n. Для вычисления этого значения factr() вызывается с n-1. Это происходит, пока n не станет равно 1.

При вычислении факториала числа 2, первый вызов factr() приводит ко второму вызову с аргументом 1. Данный вызов возвращает 1, после чего результат умножается на 2 (исходное значение n). Ответ, таким образом, будет 2. Можно попробовать вставить printf() в factr() для демонстрации уровней и промежуточных ответов каждого вызова.

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

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

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

При написании рекурсивных функций следует иметь оператор if, чтобы заставить функцию вернуться без рекурсивного вызова. Если это не сделать, то, однажды вызвав функцию, выйти из нее будет невозможно. Это наиболее типичная ошибка, связанная с написанием рекурсивных функций. Надо использовать при разработке функции printf() и getchar(), чтобы можно было узнать, что происходит, и прекратить выполнение в случае обнаружения ошибки.

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

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

Например, определим вычисление факториала в виде рекурсивной функции:

#include unsigned long long factorial(unsigned); int main() < unsigned n ; auto result < factorial(n)>; std::cout unsigned long long factorial(unsigned n) < if(n >1) return n * factorial(n-1); return 1; >

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

Рекурсивная функция обязательно должна иметь некоторый базовый вариант, который использует оператор return и к которому сходится выполнение остальных вызовов этой функции. В случае с факториалом базовый вариант представлен ситуацией, при которой n = 1. В этом случае сработает инструкция return 1; .

Например, при вызове factorial(5) получится следующая цепь вызовов:

1. 5 * factorial(4)
2. 5 * 4 * factorial(3)
3. 5 * 4 * 3 * factorial(2)
4. 5 * 4 * 3 * 2 * factorial(1)
5. 5 * 4 * 3 * 2 * 1

Другим распространенным показательным примером рекурсивной функции служит функция, вычисляющая числа Фиббоначчи. n-й член последовательности чисел Фибоначчи определяется по формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1. Значения f(0)=0 и f(1)=1, таким образом, определяют базовые варианты для данной функции:

#include unsigned long long fib(unsigned); int main() < for(unsigned i<>; i < 10; i++) < auto n = fib(i); std::cout std::cout unsigned long long fib(unsigned n)

Результат работы программы — вывод 10 чисел из последовательности Фиббоначчи на консоль:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

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

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

#include unsigned long long factorial(unsigned); int main() < unsigned n ; std::cout unsigned long long factorial(unsigned n) < unsigned long long result; for(unsigned i; i return result; >

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

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

В C++ любая функция кроме main() может вызывать саму себя. То есть в теле функции может быть размещен вызов этой же функции. Это называется рекурсией.

Когда программа выполняет код рекурсивной функции – она будет выполнять его бесконечно, если не предусмотреть условие выхода из рекурсии. Об этом надо помнить, чтобы избежать зацикливания вызовов. Поэтому в определении рекурсивной функции обязательно надо указывать условие выхода. Например, можно разместить её вызов внутри блока if .

рекурсия в C++
using namespace std ;
void recursionGoDown ( int someNumber )
cout << "Спуск по рекурсии: " << someNumber << endl ; if ( someNumber > 0 )
recursionGoDown ( someNumber — 1 ) ; // рекурсивный вызов
cout << "Возврат по рекурсии: " << someNumber << endl ; setlocale ( LC_ALL , "rus" ) ; recursionGoDown ( 9 ) ;

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

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

cout << "Возврат по рекурсии: " << someNumber << endl ;

будет выполняться тоже 10 раз, но значение someNumber будет меняться в обратном порядке. Сначала оно будет соответствовать тому, что передалось в функцию на 10 уровне рекурсии, потом тому что передалось на 9 уровне и т.д.

Хочу обратить внимание на важный момент. При каждом рекурсивном вызове создается новая переменная someNumber с новым значением. Эти переменные будут занимать какое-то место в оперативной памяти. Если вызовов 10, как в нашем примере, то и в памяти будет храниться 10 переменных с разными значениями. Можно дописать в программу вывод на экран адресов, по которым хранятся эти значения и убедиться в этом:

Рекурсия C++
using namespace std ;
void recursionGoDown ( int someNumber )
cout << "Спуск по рекурсии: " << someNumber << ". &someNumber: " << &someNumber << endl ; if ( someNumber > 0 )
recursionGoDown ( someNumber — 1 ) ; // рекурсивный вызов
cout << "Возврат по рекурсии: " << someNumber << ". &someNumber: " << &someNumber << endl ; setlocale ( LC_ALL , "rus" ) ; recursionGoDown ( 2 ) ;

Передаем в функцию число 2: recursionGoDown ( 2 ) ; Уровней рекурсии будет 3.

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

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

Но, как утверждают опытные программисты и многие авторы книг, это не значит, что рекурсия бесполезна. Есть задачи, решать которые, используя итерации циклов, сложно и громоздко. А рекурсивное решение выглядит лучше. Для начального уровня, пока вы изучаете только основы программирования на C++, вам достаточно просто понимать, что из себя представляет рекурсия и как она работает.

Посмотрите ещё видео по теме Рекурсия:

06.10.2014 | Posted in Функции, Рекурсия, Область видимости переменных

7 thoughts on “ Рекурсия в С++ ”

Вы слишком строги к рекурсии 😉 1. Рекурсия – это общий математический аппарат, которым теоретически выражаются все вычислимые алгоритмы (это я взял из мат. теории алгоритмов).
2. Все задачи над динамическими структурами данных (списки, очереди, деревья, графы, …) решаются рекурсивно проще, а главное нагляднее, чем итерационно (итерационные циклические алгоритмы лучше работают над массивами – статическими конструкциями).
3. Есть алгоритмы, которые выражаются в 2-3 строчки рекурсивно, но которые крайне сложно выписать без рекурсии. Красивейший пример тому: знаменитая задача “Ханойская башня”. Многие алгоритмы сортировки (тех же массивов) лучше выражаются в рекурсивной форме. Рекурсия только кажется сложной, потому что ей не учат в отечественной практике и не умеют её применять. А в университетах Франции, например, обучение 1-го семестра начинают с обучения рекурсивным алгоритмам.

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

Azizjan Ayupov :
Как вы предлагаете использовать рекурсию в списках и очередях?

Рекурсия – это самый естественный способ обработки любых динамических структур (списков, деревьев и т.д.), это демонстрируют функциональные языки программирования, такие как Lisp. Такой подход намного эффективней, чем итерационный (циклами). Но это нужно показывать на примерах кода…
А простой и красивый пример рекурсии посмотрите в задаче возведения числа в степень: https://purecodecpp.com/archives/2734

Здравствуйте.
Объясните пожалуйста следующие моменты, всю голову сломал, не могу понять:
1. Если в массив в процессе деления на подмассивы не длиться ровно на 2, то программа прекратит работу? Ведь в int middle= arr[(l+r)]/2 , где (l+r)/2- целое число. 2. Если в массиве есть повторяющиеся числа, и у опорного элемента будет такое же число, как у числа слева или справа, например 1,2,3, 5, 6,5,7
то, не получится что после того, как программа определила центральный элемент =5, и начала его сравнение с элементами правого подмассива , она дойдя до одинакового элемента arr [5]=5 подумает что достигла центрального элемента , перестанет сравнивать более ранние элементы (arr [4>, arr [3]) с центральным, примет этот 5 элемент за центральный, и далее будет считать его крайней левой границей? 3. В примере рассматривалась попарная смена (слева и справа от центрального) элементов, не удовлеторяющих условию: while (middle>arr [i]) i++;
while (middle swap (arr [i], arr [j]);
i++;
j–; > А что если либо изначально, либо после процесса сортировки остался 1
подлежащий замене элемент, например:
1, 2, 3, 8, 5, 6, 7, 9,10
то если я правильно понял, он поменяется с центральным элементом,
т.е. получится 1,2,3,5, 8, 6,7,9,10 ? 4. Значение центрального элемента может поменяется. В то же время после такого изменения центрального элемента, сравнения, произведенные с более ранним центральным элементом окажутся неверными, т.к они не пересматриваются, и продолжают идти дальше. В результате сортировка окажется неверной. Например:
исходный массив: 1,2,6,9, 4, 10,11,3, 12 с центральным элементом 4.
После первой замены (6 на 3) получается: 1,2,3,9, 4, 10,11,6,12.
После второй замены (9 на 4) получается: 1,2,3,4, 9, 10,11,6,12 и сортировка этого множества заканчиватся. Однако элемент правого подмножества 6 отсортирован неправильно.

Максат :

интересно, я освоил рекурсию и вот начал уже решать задачки на эту тему с сайта acmp.ru, и вот на такую задачу наткнулся:
Сумма кубов
(Время: 1 сек. Память: 16 Мб Сложность: 52%) Известно, что любое натуральное число можно представить в виде суммы не более чем четырех квадратов натуральных чисел. Вася решил придумать аналогичное утверждение для кубов – он хочет узнать, сколько кубов достаточно для представления любого числа. Его первая рабочая гипотеза – восемь. Выяснилось, что почти все числа, которые Вася смог придумать, представляются в виде суммы не более чем восьми кубов. Однако число 239, например, не допускает такого представления. Теперь Вася хочет найти какие-либо другие такие числа, а также, возможно, какую-либо закономерность в представлениях всех остальных чисел, чтобы выдвинуть гипотезу относительно вида всех чисел, которые не представляются в виде суммы восьми кубов. Помогите Васе написать программу, которая проверяла бы, возможно ли представить данное натуральное число в виде суммы не более чем восьми кубов натуральных чисел, и если это возможно, то находила бы какое-либо такое представление.
Входные данные Во входном файле INPUT.TXT записано натуральное число N (1 ≤ N ≤ 2×109).
Выходные данные В выходной файл OUTPUT.TXT выведите не более восьми натуральных чисел в порядке невозрастания, кубы которых в сумме дают N. Если вариантов несколько, то выведите любой. Если искомого представления не существует, то в выходной файл необходимо вывести слово IMPOSSIBLE.
Примеры
№ INPUT.TXT OUTPUT.TXT
1 17 2 2 1
2 239 IMPOSSIBLE Думал что дп и даже код написал, а позже понял что вектора такого размера просто не существует, пожалуйста помогите решить данную задачу

rtorque :

Непонятно, почему рекурсия начинает выдавать значения в обратном порядке, в коде ничего такого не видно:
void recursionGoDown(int someNumber)
cout recursionGoDown(someNumber – 1); // рекурсивный вызов
>
cout >
По-идее, как только someNumber делается равным 0, условие оператора if становится ложным и блок должен просто игнорироваться. Но вместо этого он выполняется в обратном порядке. Как это дерьмо устроено.

Как работает рекурсия – объяснение в блок-схемах и видео

Представляю вашему вниманию перевод статьи Beau Carnes How Recursion Works — explained with flowcharts and a video.

«Для того чтобы понять рекурсию, надо сначала понять рекурсию»

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

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

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

Есть два основных подхода в создании алгоритма для решения данной проблемы: итеративный и рекурсивный. Вот блок-схемы этих подходов:

Какой подход для Вас проще?

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

function look_for_key(main_box) < let pile = main_box.make_a_pile_to_look_through(); while (pile is not empty) < box = pile.grab_a_box(); for (item in box) < if (item.is_a_box()) < pile.append(item) >else if (item.is_a_key()) < console.log("found the key!") >> > >

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

function look_for_key(box) < for (item in box) < if (item.is_a_box()) < look_for_key(item); >else if (item.is_a_key()) < console.log("found the key!") >> >

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

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

Граничный и рекурсивный случай

То, что Вам необходимо принять во внимание при написании рекурсивной функции – это бесконечный цикл, т.е. когда функция вызывает саму себя… и никогда не может остановиться.
Допустим, Вы хотите написать функцию подсчета. Вы можете написать ее рекурсивно на Javascript, к примеру:

// WARNING: This function contains an infinite loop! function countdown(i) < console.log(i) countdown(i - 1) >countdown(5); // This is the initial call to the function.

Эта функция будет считать до бесконечности. Так что, если Вы вдруг запустили код с бесконечным циклом, остановите его сочетанием клавиш «Ctrl-C». (Или, работая к примеру в CodePen, это можно сделать, добавив “?turn_off_js=true” в конце URL.)

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

И снова функция подсчета, только уже с граничным случаем:

function countdown(i) < console.log(i) if (i else < // recursive case countdown(i - 1) >> countdown(5); // This is the initial call to the function.

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

Сначала мы выведем цифру 5, используя команду Console.Log. Т.к. 5 не меньше или равно 1, то мы перейдем в блок else. Здесь мы снова вызовем функцию и передадим в нее цифру 4 (т.к. 5 – 1 = 4).

Мы выведем цифру 4. И снова i не меньше или равно 1, так что мы переходим в блок else и передаем цифру 3. Это продолжается, пока i не станет равным 1. И когда это случится мы выведем в консоль 1 и i станет меньше или равно 1. Наконец мы зайдем в блок с ключевым словом return и выйдем из функции.

Стек вызовов

Рекурсивные функции используют так называемый «Стек вызовов». Когда программа вызывает функцию, функция отправляется на верх стека вызовов. Это похоже на стопку книг, вы добавляете одну вещь за одни раз. Затем, когда вы готовы снять что-то обратно, вы всегда снимаете верхний элемент.

Я продемонстрирую Вам стек вызовов в действии, используя функцию подсчета факториала. Factorial(5) пишется как 5! и рассчитывается как 5! = 5*4*3*2*1. Вот рекурсивная функция для подсчета факториала числа:

function fact(x) < if (x == 1) < return 1; >else < return x * fact(x-1); >> 

Теперь, давайте посмотрим что же происходит, когда вы вызываете fact(3). Ниже приведена иллюстрация в которой шаг за шагом показано, что происходит в стеке. Самая верхняя коробка в стеке говорит Вам, что вызывать функции fact, на которой вы остановились в данный момент:

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

Нашли уже ключ?

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

Но в рекурсивном подходе нет стопки. Так как тогда алгоритм понимает в какой коробке следует искать? Ответ: «Стопка коробок» сохраняется в стеке. Формируется стек из наполовину выполненных обращений к функции, каждое из которых содержит свой наполовину выполненный список из коробок для просмотра. Стек следит за стопкой коробок для Вас!

И так, спасибо рекурсии, Вы наконец смогли найти свой ключ и взять рубашку!

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

Заключение от автора

Надеюсь, что статья внесла немного больше ясности в Ваше понимание рекурсии в программировании. Основой для статьи послужил урок в моем новом видео курсе от Manning Publications под названием «Algorithms in Motion». И курс и статься написаны по замечательной книге «Grokking Algorithms», автором которой является Adit Bhargava, кем и были нарисованы все эти замечательные иллюстрации.

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

От себя хочу добавить, что с интересом наблюдаю за статьями и видеоуроками Beau Carnes, и надеюсь что Вам тоже понравилась статья и в особенности эти действительно замечательные иллюстрации из книги A. Bhargav «Grokking Algorithms».

• рекурсия
• алгоритмы
• обучение программированию
• образование
• javascript
• перевод