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

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

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

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

Рассмотрим эту программу подробнее. Это важный момент.
Сначала пишется главная функция: int main(). Это пустая программа, написанная на C++. После написания пустой программы начинается написание рекурсивной функции. В приведенном примере я новую функцию назвал int sum(int n)
Наша функция должна посчитать сумму элементов. Для упрощения берём целые числа. Функция будет что-то считать, в нашем случае функци будет выполнять сложение чисел. Результат сложения функция будет отдавать, как результат своих усилий. Этот результат можно будет забрать в любой нужный момент извне функции. Так как числа выбраны целые, то результат суммы целых чисел — это целое число, поэтому для возвращаемого результата используется целый тип, говорим функции, что она будет возвращать int.

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

А теперь смотрите, что происходит:
Вовнутрь функции отдано число 5. Функция вызвана и начала работу. n принял 5, происходит проверка, что в n, где выясняется, что в n не один, поэтому возвращается какое-то число. Если вы помните, то были выбраны целые числа, а возвращаемый результат можно забрать в любой нужный момент извне функции. Забирается результат из мегасхожей функции, на самом деле из новой функции, которая будет копией оной. Та функция, которая не копия, ещё выполняет свою работу, она ждёт того значения, которое её надо будет отдать. Можете считать, что эта не копия приняла режим ожидания. Начинает работу копия. Смотрите, что в эту копию приходит, в неё приходит (n-1). В неё приходит 5-1, что есть 4. Первая функция ждёт своего значения, копия первой функции принимает режим ожидания, начинает ждать своего значения, которое должна будет вернуть копия этой копии. И так повторяется до тех пор, пока не случится 2-1, отчего в n прийдёт 1. Как только в n прийдёт 1, сработает return последней созданной на тот момент времени копии. В текущей программе указано, что если в n приходит 1, то возвращается 1. Этот момент прекращения рекурсии является началом расчёта. Вот такой хитрый вираж происходит.

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

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

Подводим итоги, вспоминаем, как писали программу.
1) Пишем пустой блок главной программы.
2) Пишем рекурсивную функцию.
3) Вызываем рекурсивную функцию из главного блока программы.

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

Все комментарии на сайте проверяются, поэтому ваш комментарий может появиться не сразу. Для вставки кода в комментарий используйте теги: [php]ВАШ_КОД[/php]

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

  • Varg говорит:

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

    {
    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 говорит:

    gde tut oshibka???

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

  • Иван Иванов говорит:

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

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

  • Сергей Сергеев говорит:

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

  • Дмитрий говорит:

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

    • admin говорит:

      Это вообще неправильное решение. Вместо суммы чисел от 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 ничего противозаконного тут не делают, хоть это и из Си. Так не по плюсовски, но так можно.

  • Юлия говорит:

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

     

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

Ваш e-mail не будет опубликован.

Поиск

 
     

Яндекс.Метрика

НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

- Я тут котёнка завела. Помоги придумать какое-нибудь компьютерное имя... - Мышка! - Ты чё, это же котик! - Ну, тогда БЛОХ ПИТАНИЕ.

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок