Рекурсия в С





рекурсия с++, Фібоначчі 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′ (Автор видео: Денис Марков).

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


Згоден отримувати повідомлення від purecodecpp.com на мій e-mail

дата
сторінка
Рекурсія C++
рейтинг
5

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

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

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

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

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

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

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

Код розміщуйте в тегах: <pre class="lang:C ++ декодуванням:true ">ВАШ КОД</заздалегідь>