Функции в С++ для начинающих. Рекурсия

Опубликовано 05.04.2012 | Автор: admin

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

В программировании рекурсией называют зацикливание функций путём вызовов функций вызовами функций.

Различают прямую рекурсию и косвенную:
- Прямая — это прямой вызов из некоторой функции этой же самой функции.
- Косвенная — это вызов из первой функции второй функции, когда вторая функция в своём вычислении использует первую функцию.

Для понимания этой статьи необходимо знать:

Желательно знать:

Простейший пример использования прямой рекурсии:

#include <iostream>

using namespace std;

void foo(int x=5) {			//Функция foo c одним параметром
	cout << x << '\n';
	if (x)	foo(x-1);		//Обращаемся к функции foo с одним параметром
}

int main() {
	foo();			//Провоцируем запуск функции foo
	cin.get();
}

#include <iostream>

using namespace std;

void foo(int x=5) { //Функция foo c одним параметром

cout << x << '\n';

if (x) foo(x-1); //Обращаемся к функции foo с одним параметром

}

int main() {

foo(); //Провоцируем запуск функции foo

cin.get();

}

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

В показанном примере при каждом новом вызове функции foo мы изменяем параметр: отдаём аргумент на единицу меньший, чем последний отданный. Таким образом мы стремимся к нулю или к какому-нибудь отрицательному значению. Это значение используется как выключатель рекурсивных вызовов. Т. е. перед рекурсивным вызовом мы обязательно должны выполнять проверку, достигнута ли контрольная точка для срабатывания выключателя, если нет, то запускаем функцию снова, а если достигнута, то не вызываем функцию. Если этой проверки не сделать, то получится эффект бесконечно рекурсии, из-за которой сломается программа. Природа рекурсии — цикл, но в отличие от непосредственных циклов — рекурсия работает немного иначе, каждый рекурсивный вызов требует себе памяти. Жрёт память рекурсия с аппетитом. При большом количестве рекурсивных вызовов памяти просто не хватает, поэтому в отличие от использования обычных циклов, когда программа зависает, рекурсия программу не вешает, а обычно просто валит/ломает, при этом программа жалуется на переполнение стека.

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

Каждый новый рекурсивный вызов — это создание в памяти нового экземпляра функции. Т. е. сколько рекурсивных вызовов происходит — столько в памяти висит экземпляров функций.

Простейший пример использования косвенной рекурсии:

#include <iostream>

void foo1(int);         //Прототипы функций
void foo2(int);

using namespace std;

void foo1(int x) {
	cout << x << '\n';
		foo2(x-1);		        //foo1 задействует foo2
}

void foo2(int x=5){
    if (x) foo1(x);             //foo2 задействует foo1
}

int main() {
	foo2();			    //Провоцируем запуск функции foo2
	cin.get();
}

#include <iostream>

void foo1(int); //Прототипы функций

void foo2(int);

using namespace std;

void foo1(int x) {

cout << x << '\n';

foo2(x-1); //foo1 задействует foo2

}

void foo2(int x=5){

if (x) foo1(x); //foo2 задействует foo1

}

int main() {

foo2(); //Провоцируем запуск функции foo2

cin.get();

}

О рекурсии иногда говорят, что она не нужна, что использовать её плохо и всячески стараются очернять. На самом деле рекурсивные коды всегда выглядят лаконично и красиво. Если вы видите иерархию папок, выстроенную в виде дерева, то на 99,9% для вычисления использована рекурсия. Многие фундаментальные алгоритмы, до которых вы однажды дойдёте, если будете серьёзно изучать языки программирования, описаны с помощью рекурсивных функций. Некоторые сортировки используют рекурсивные функции (быстрая сортировка). Т. е. люди не стесняются применять рекурсивные функции, а все эти заявители о бессмысленности рекурсии могут, конечно, иметь свою точку зрения, но по-моему понимать и применять рекурсию должны уметь все, кто занимается программированием. Рекурсия является важной темой, подробно разбираемой в специальных курсах программирования.

Согласно правилам языка С++ — нельзя рекурсить функцию main.

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

Шаг рекурсии выполняется при еще не закрытом исходном вызове функции, т. е. когда исполнение функции еще не закончилось. Каждый шаг рекурсии — это затраты времени на создание нового экземпляра функции и затраты памяти на удержание в памяти всех экземпляров функций, порождённых рекурсией. Шаги рекурсии прекращаются с достижением контрольной точки, описанной программистом. (Чуть выше мы стремились от положительного числа к нулю и решили, что контрольной точкой у нас должен быть ноль, при достижении нуля рекурсивные вызовы прекращались и функции, начиная с последнего созданного экземпляра, поочереди завершали свою работу)

Задача:

С помощью рекурсии вывести на экран сумму натуральных чисел от 1 до N

//Рекурсия.		Сумма чисел от 1 до N
#include <iostream>

using namespace std;

//рекурсивная функция
int sum(int n)  //В качестве параметра будет передаваться число из места вызова в переменную n
{
	if (n == 1) return 1;  //если новое значение 1, то будем складывать его с 1, а не с предыдущим. т. к. предыдущее - это ноль. и сложение 1+0 будет бесконечным.
	else return sum(n - 1) + n; //но если n>1, то складываем его с предыдущим значением, равным сумме всех элементов до n
}

int main()
{
	cout << "1..5: " << sum(5) << endl; // передаем в функцию sum аргумент 5. n принимает значение 5
	cout << "1..6: " << sum(6) << endl; // передаем в функцию sum аргумент 6. n принимает значение 6
	cout << "1..7: " << sum(7) << endl; // передаем в функцию sum аргумент 7. n принимает значение 7
	cin.get();
}

//Рекурсия. Сумма чисел от 1 до N

#include <iostream>

using namespace std;

//рекурсивная функция

int sum(int n) //В качестве параметра будет передаваться число из места вызова в переменную n

{

if (n == 1) return 1; //если новое значение 1, то будем складывать его с 1, а не с предыдущим. т. к. предыдущее - это ноль. и сложение 1+0 будет бесконечным.

else return sum(n - 1) + n; //но если n>1, то складываем его с предыдущим значением, равным сумме всех элементов до n

}

int main()

{

cout << "1..5: " << sum(5) << endl; // передаем в функцию sum аргумент 5. n принимает значение 5

cout << "1..6: " << sum(6) << endl; // передаем в функцию sum аргумент 6. n принимает значение 6

cout << "1..7: " << sum(7) << endl; // передаем в функцию sum аргумент 7. n принимает значение 7

cin.get();

}

Поскольку мы не знаем заранее, сколько у нас рекурсивных шагов получится, мы забиваем память экземплярами функций, при этом первый созданный экземпляр функции оказывается в самом хвосте отдачи результатов: функции при рекурсии срабатывают наизнанку. По этой причине мы отталкиваемся не от последнего вычисления, создавая контрольную точку, а от первого: первая рекурсивная функция выполняется последней, вторая предпоследней и т. д. Контрольной точкой в показанном примере мы сделали единицу. А чтобы эта единица могла быть достигнута, при каждом новом вызове функции мы уменьшаем уходящий в функцию аргумент на 1. Если n принял единицу, то возвращается единица, иначе функция вызывает саму себя. Вот этот момент важно словить, это и есть рекурсия. Когда мы отдаём аргументом в функцию число 5, у нас в памяти в один момент времени оказывается 5 скопированных экземпляров функций, когда 6 — 6 экземпляров, когда 7 — 7 экземпляров.

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

Вот мы запустили функцию суммирования чисел от 1 до 5. Как работает созданная нами рекурсивная функция? — Срабатывает функция sum, в которой параметр подбирает значение 5, значение параметра проверяется с контрольной точкой: 5 == 1?, поскольку равенство ложно, создаётся новый экземпляр функции, в которую уходит значение 5-1, в этом новом экземпляре проверяется равенство 4 == 1? … в какой-то момент времени в функцию отдаётся значение 2-1, проверяется равенство 1 == 1?, условие верно, функция завершается и отдаёт результатом своих действий число 1. Вот этот первый завершённый экземпляр провоцирует отдачу цепочки результатов: все созданные экземпляры начинают отдавать свои результаты, вычисленные из параметров: 5,4,3,2,1. Каждый результат складывается со значением актуального для функции значением параметра:
Создание цепочки копий функции, звенья которой прекращают создаваться при достижении контрольной точки, т. е. при достижении n значения 1.
Отдача результатов, с последнего созданного экземпляра функции:
Параметр 1: возврат 1
Параметр 2: возврат sum(n-1) + n ==> sum(2-1) + 2 ==> 1 + 2 ==> 3 ==> возврат 3
Параметр 3: возврат sum(n-1) + n ==> sum(3-1) + 3 ==> 3 + 3 ==> 6 ==> возврат 6
Параметр 4: возврат sum(n-1) + n ==> sum(4-1) + 4 ==> 6 + 4 ==> 10 ==> возврат 10
Параметр 5: возврат sum(n-1) + n ==> sum(5-1) + 5 ==> 10 + 5 ==> 15 ==> возврат 15

В этом раскладе вам нужно понять, что sum(n-1) вычисляет некоторое значение в другом экземпляре функции, а n — это актуальное значение для текущей функции, т. е не надо думать о том, что в этой формуле обе n обозначают одно и то же значение: слева результат работы функции для аргумента n-1, а справа да, прямое значение параметра текущей функции.

Любую рекурсию теоретически можно заменить обычными циклами.

Рекурсии требуют больше времени и памяти, чем требуют обычные циклы.

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

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

Основной недостаток рекурсии — издержки времени на создание экземпляров функций и прожорливость к памяти.

В завершение этой статьи приведу другое решение задачи на сложение чисел использованием рекурсии:

//Рекурсия		Сумма чисел от 1 до N
#include <iostream>
#include <iomanip>      //setw

using namespace std;

void sum(int value, int result=0){
    if (value){
            result = value + result;
            sum(value-1, result);           //рекурсивный вызов
    } else {
        cout << result << setw(5);          //ели достигнута контрольная точка, выводим результат на экран
    }
}

int main(){

    for (int i=0; i<50; i++){                   //Будем смотреть несколько результатов
        cout << 1 << ".." << i << " == ";
        sum(i);                                 //вызов функции sum
        cout << '\n';
    }
    cin.get();
}

//Рекурсия Сумма чисел от 1 до N

#include <iostream>

#include <iomanip> //setw

using namespace std;

void sum(int value, int result=0){

if (value){

result = value + result;

sum(value-1, result); //рекурсивный вызов

} else {

cout << result << setw(5); //ели достигнута контрольная точка, выводим результат на экран

}

int main(){

for (int i=0; i<50; i++){ //Будем смотреть несколько результатов

cout << 1 << ".." << i << " == ";

sum(i); //вызов функции sum

cout << '\n';

}

cin.get();

}

Рубрика: Знакомства, Решения задач, Функции

Varg:

17.03.2014 в 5:07 пп

Добрый день, упорото ни могу понять как производит вычисления данная функция
{ if (n==1) return 1; //если новое значение 1, то будем складывать его с 1, а не с предыдущим. т.к. предыдущее - это ноль. и сложение 1+0 будет бесконечным. else return sum(n-1)+n; //но если n>1, то складываем его с предыдущим значением, равным сумме всех элементов до n }По моему разумению в n находиться 5 условие не совпадает тогда выполняется данный код sum(n-1)+n то есть к 5 прибавляется что то полученное в скобках путем вычитания но что ( 5 - 1 )+5 и если так то что останавливает данное арифметическое действие :?: :?: :?: Что за предыдущее значение, откуда оно берется чему равно :?: :?: :?:


Автор сайта отвечает:

Грубо говоря.

есть переменная x, есть функция my_func() и результат этой функции Result

В переменную можно присвоить результат работы функции.

x=my_func() ==> обозначает, что в X присвоится значение переменной Result

Текущее состояние x будет исходным состоянием (или можно назвать предыдущим),

________________________________________________

Так как в функцию можно передавать параметры, то возьму 2 параметра/ Пусть функции их же и отдают

x=my_func(5) ==> //Значит x станет равен 5 (исходное состояние)

x=x+my_func(7) ==//Исходное состояние + следущее состояние, ну и можно сказать, что  прошлое + текущее

________________________________________________

Когда выполняется рекурсия, то функция выполняет саму себя

В указанном коде

sum(n-1)  ==> это функция. Внутри функции выполняется функция. Т.к. В функцию передается n-1, то при каждом новом вызове n внутри функции уменьшается на единичку. Честно говоря не знаю как понятно объяснить. Тут как бы переменная не убивается, а наоборот упрямо исследуется пока выполняется рекурсия.

sum(n-1)+n равносильно сложению двух слагаемых, где sum(n-1) это первое и обозначает вызов функции, а не простое действие или значение, а второе обозначает обычную переменную.

________________________________________________

Вот как-то так понимать нужно. На сайте по рекурсии по личному моему мнению неплохой и более наглядный пример http://ci-plus-plus-snachala.ru/?p=24

Да почти все так как я и понял (в последнем абзаце вы показали рекурсию))), но остаться вопрос как получается сумма, которая потом вы водиться на экран ?

Я работаю с Dev C++ у меня данный пример выводит сумму ==15, если по считать как написано в примере то сумма получается другой.

Я писал выше вот возьмем (5-1)+5=4+5=9

И еще не совсем логично получается  в 8й строке если поменять возвращаемое число с return 1  на 2 сумма меняется на 16 как это условие связано с 9й строкой ?
Автор сайта отвечает:

1+2+3+4+5 = 15. Пример правильно выводит.
(5) //В функцию дали 5, проверили ее на равенство с единицей. не равно, вызвали функцию снова, отдав в нее 5-1

(5-1+(5)) //...

(4-1+(5-1+(5)))

(3-1+(4-1+(5-1+(5))))

(2-1+(3-1+(4-1+(5-1+(5)))))
2-1 == 1, закончили вызывать функцию.

(2-1+(3-1+(4-1+(5-1+(5))))) == 15

это и есть результат.

Здесь результат работы функции - это разность первых двух чисел, а n - это вся остальная часть справа

__________________________________

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

Да да да не успел написать, что понял, все верно, что то сразу не дошло. Спасибо вам хороший сайт))

 

И еще не совсем логично получается в 8й строке если поменять возвращаемое число с return 1 на 2 сумма меняется на 16 как это условие связано с 9й строкой ?

С этим тоже все понятно просто return 2 добавляет к сумме так сказать свою лишению денницу.
Автор сайта отвечает:

не лишнюю денницу, а эту двойку, а если написать -3, то при сложении один раз будет отнимать тройку и т.д.

Вся логика в том, что любой рекурсивной функции нужна точка возврата.

Связь с девятой строкой в том, что в функцию sum при вызове её из внутри main передается число, при рекурсивных вызовах это число каждый раз уменьшается на единицу (n-1), этот результат n-1 проверяется на  равенство с единицей и если равенство истинно, то вся полученная сумма будет просуммирована с тем числом, который в том return. иначе вся общая сумма будет просуммирована с этим новым n-1

Ответить

Zara:

06.11.2014 в 4:39 пп

#include <iostream>
using namespace std;

bool negative(int a[],int n)

{
if(a[n-1]<0)
return true;
else

return false;
negative(a,n-1);
}
int main()
{
int a[10],n; 
for(int i=0;i<=n;++i)
{
cin>>a[i];
}
cout<<negative(a,n);
}

bool negative(int a[],int n)

if(a[n-1]<0)

return true;

else

return false;

negative(a,n-1);

int a[10],n;

for(int i=0;i<=n;++i)

cin>>a[i];

cout<<negative(a,n);

gde tut oshibka???

Автор сайта отвечает
первая ошибка в том, что int a[10],n; (n не определена, надо задавать значение)
вторая ошибка в том, что внутри цикла несколько раз с клавиатуры считывается значение. И не каждый раз выполняется вывод на экран, а только для последнего считанного значения.

Иван Иванов:

17.12.2014 в 3:58 пп

Думаю, что рекурсия имеет место быть в академическом программировании, а вот в практическом её применять, имхо, не стоит. Язык С/С++ предназначен не только для ПК, но и для программирования других устройств, в которых размер памяти может быть очень небольшим. А так как рекурсия на каждой итерации «отъедает» память, то вполне может возникнуть переполнение стека. Потом придётся переписывать программу и объяснять заказчику, что ты не верблюд.
А сайт хороший! Многие вещи очень доходчиво объясняются. Спасибо!

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

Сергей Сергеев:

17.03.2015 в 12:20 пп

DOM модель (деревья-списки нод-узлов-тегов) без рекурсии создать гораздо сложнее. Осуществлять поиск/обработку по такому дереву тоже. Т.е. рекурсия применяется в программировании повсеместно. Тот же web. Для ускорения обычно используется спецификатор inline (подстановка кода ф-ции вместо вызова по адресу). Но современные компиляторы часто осуществляют такую подстановку и без спецификатора inline.

Дмитрий:

11.05.2015 в 3:40 дп

int rec(int n, int sum)
{
if(sum<n) sum+=rec(n, sum+1);
else return n;
}

void main()
{
int n, sum=1;
scanf("%d", &n);
printf("%d", rec(n, sum));
getch();
}

int rec(int n, int sum)

if(sum<n) sum+=rec(n, sum+1);

else return n;

void main()

int n, sum=1;

scanf("%d", &n);

printf("%d", rec(n, sum));

getch();

Извиняюсь за применение printf, scanf)))
Вот как я поначалу написал, здесь зацикливания не будет если ввести 0, а просто вернет 0.
Правда надо передать два значения.

admin:

11.05.2015 в 4:52 пп

Это вообще неправильное решение. Вместо суммы чисел от 1 до n у вас просто sum увеличивается на единичку.
должно быть 1+2+3+4…., а здесь 1+1=2 (2<n?) нет, 2+1=3 (3<n? нет), 3+1=4 и т.д.

никогда не нужно писать void main(), только int main() — это уже закон. Хотя на сайте есть примеры с void main(), но так давно уже нельзя.

а printf, scanf ничего противозаконного тут не делают, хоть это и из Си. Так не по плюсовски, но так можно.

Ответить

Юлия:

20.12.2016 в 7:38 пп

Спасибо! Очень доступно написано! Наконец-то я врубилась:)

Анна:

29.06.2017 в 5:53 пп

Добрый день! Помогите, пожалуйста, решить задачу с использованием рекурсивной функции на С++!!! желательно попроще( т.к. новичок в этом деле, чтобы смогла понять)

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

Последние комментарии

Александр к записи Хороший стиль программирования
Аноним к записи Список тем сайта
Аноним к записи Список тем сайта

Функции в С++ для начинающих. Рекурсия

8 комментариев на «“Функции в С++ для начинающих. Рекурсия”»

Добавить комментарий Отменить ответ

Поиск

Последние темы

Случайная книга в электронном формате

Последние комментарии

Мета