Рекурсия в С





рекурсия с++, Фібоначчі 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. Такий підхід набагато ефективніше, ніж ітераційний (циклами). Але це потрібно показувати на прикладах коду…
        А простий і красивий приклад рекурсії подивіться в завданні піднесення числа до степеня: https://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 (середній>arr [i]) i ;
    while (середній<arr [j]) j–;

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

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

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