Рекурсия в С





рекурсия с++, Фібоначчі C ++

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

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

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

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

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

рекурсия с++, Фібоначчі C ++

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

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

рекурсия с++, Фібоначчі C ++

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

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

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

Посмотрите ещё видео по теме Рекурсия с 6′ (Автор видео: Денис Марков).

Нові уроки з програмування:

Рекурсия в С
4.5 (90%) 4 голосів

5 думки про "Рекурсия в С

  1. Ви занадто суворі до рекурсії ;-)

    1. рекурсія – це загальний математичний апарат, яким теоретично виражаються все обчислюваності алгоритми (це я взяв з мат. теорії алгоритмів).
    2. Всі завдання над динамічними структурами даних (списки, черги, дерева, графи, …) вирішуються рекурсивно простіше, а головне наочніше, ніж ітераційно (ітераційні циклічні алгоритми краще працюють над масивами – статичними конструкціями).
    3. є алгоритми, які виражаються в 2-3 рядки рекурсивно, але які вкрай складно виписати без рекурсії. Найгарніший приклад того: знаменита завдання “Ханойська вежа”. Багато алгоритми сортування (тих же масивів) краще виражаються в рекурсивної формі.

    Рекурсія тільки здається складною, тому що їй не вчать у вітчизняній практиці і не вміють її застосовувати. А в університетах Франції, например, навчання 1-го семестру починають з навчання рекурсивним алгоритмам.

    1. Завжди добре, коли хтось висловлює свою точку зору і свою особисту думку, засноване на досвіді. Початківцям корисно буде почитати.

      1. рекурсія – це найприродніший спосіб обробки будь-яких динамічних структур (списків, дерев і т.д.), це демонструють функціональні мови програмування, такі як Lisp. Такий підхід набагато ефективніше, ніж ітераційний (циклами). Але це потрібно показувати на прикладах коду…
        А простий і красивий приклад рекурсії подивіться в завданні піднесення числа до степеня: http://purecodecpp.com/archives/2734

  2. Вітаю.
    Объясните пожалуйста следующие моменты, всю голову сломал, не можу зрозуміти:
    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<arr [j]) j–;

    if (i<=j)
    {
    своп (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 отсортирован неправильно.

залишити коментар

Ваша електронна адреса не буде опублікований. Обов'язкові поля позначені * *