Как работает рекурсия – объяснение в блок-схемах и видео

Представляю вашему вниманию перевод статьи Beau Carnes How Recursion Works — explained with flowcharts and a video.


«Для того чтобы понять рекурсию, надо сначала понять рекурсию»

Рекурсию порой сложно понять, особенно новичкам в программировании. Если говорить просто, то рекурсия – это функция, которая сама вызывает себя. Но давайте попробую объяснить на примере.


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


Вы открываете коробку только чтобы найти… еще больше коробок. Коробки внутри коробок и вы не знаете, в какой из них Ваш ключ. Вам срочно нужна рубашка, так что вам надо придумать хороший алгоритм и найти ключ.


Есть два основных подхода в создании алгоритма для решения данной проблемы: итеративный и рекурсивный. Вот блок-схемы этих подходов:




Какой подход для Вас проще?


В первом подходе используется цикл while. Т.е. пока стопка коробок полная, хватай следующую коробку и смотри внутрь нее. Ниже немного псевдокода на Javascript, который отражает то, что происходит (Псевдокод написан как код, но больше похожий на человеческий язык).


function look_for_key(main_box) {
  let pile = main_box.make_a_pile_to_look_through();
  while (pile is not empty) {
    box = pile.grab_a_box();
    for (item in box) {
      if (item.is_a_box()) {
        pile.append(item)
      } else if (item.is_a_key()) {
        console.log("found the key!")
      }
    }
  }
}

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


function look_for_key(box) {
  for (item in box) {
    if (item.is_a_box()) {
      look_for_key(item);
    } else if (item.is_a_key()) {
      console.log("found the key!")
    }
  }
}

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


Поскольку рекурсия используется во многих алгоритмах, очень важно понять как она работает. Если рекурсия до сих пор не кажется Вам простой, не беспокойтесь: Я собираюсь пройтись еще по нескольким примерам.


Граничный и рекурсивный случай


То, что Вам необходимо принять во внимание при написании рекурсивной функции – это бесконечный цикл, т.е. когда функция вызывает саму себя… и никогда не может остановиться.
Допустим, Вы хотите написать функцию подсчета. Вы можете написать ее рекурсивно на Javascript, к примеру:

// WARNING: This function contains an infinite loop!
function countdown(i) {
  console.log(i)
  countdown(i - 1)
}
countdown(5);    // This is the initial call to the function.


Эта функция будет считать до бесконечности. Так что, если Вы вдруг запустили код с бесконечным циклом, остановите его сочетанием клавиш «Ctrl-C». (Или, работая к примеру в CodePen, это можно сделать, добавив “?turn_off_js=true” в конце URL.)


Рекурсивная функция всегда должна знать, когда ей нужно остановиться. В рекурсивной функции всегда есть два случая: рекурсивный и граничный случаи. Рекурсивный случай – когда функция вызывает саму себя, а граничный – когда функция перестает себя вызывать. Наличие граничного случая и предотвращает зацикливание.


И снова функция подсчета, только уже с граничным случаем:

function countdown(i) {
  console.log(i)
  if (i <= 1) {  // base case
    return;  
  } else {       // recursive case
    countdown(i - 1)
  }
}
countdown(5);    // This is the initial call to the function.


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


Сначала мы выведем цифру 5, используя команду Console.Log. Т.к. 5 не меньше или равно 1, то мы перейдем в блок else. Здесь мы снова вызовем функцию и передадим в нее цифру 4 (т.к. 5 – 1 = 4).


Мы выведем цифру 4. И снова i не меньше или равно 1, так что мы переходим в блок else и передаем цифру 3. Это продолжается, пока i не станет равным 1. И когда это случится мы выведем в консоль 1 и i станет меньше или равно 1. Наконец мы зайдем в блок с ключевым словом return и выйдем из функции.


Стек вызовов


Рекурсивные функции используют так называемый «Стек вызовов». Когда программа вызывает функцию, функция отправляется на верх стека вызовов. Это похоже на стопку книг, вы добавляете одну вещь за одни раз. Затем, когда вы готовы снять что-то обратно, вы всегда снимаете верхний элемент.


Я продемонстрирую Вам стек вызовов в действии, используя функцию подсчета факториала. Factorial(5) пишется как 5! и рассчитывается как 5! = 5*4*3*2*1. Вот рекурсивная функция для подсчета факториала числа:


function fact(x) {
  if (x == 1) {  
    return 1;  
  } else {      
    return x * fact(x-1);
  }
}

Теперь, давайте посмотрим что же происходит, когда вы вызываете fact(3). Ниже приведена иллюстрация в которой шаг за шагом показано, что происходит в стеке. Самая верхняя коробка в стеке говорит Вам, что вызывать функции fact, на которой вы остановились в данный момент:



Заметили, как каждое обращение к функции fact содержит свою собственную копию x. Это очень важное условие для работы рекурсии. Вы не можете получить доступ к другой копии функции от x.


Нашли уже ключ?


Давайте кратенько вернемся к первоначальному примеру поиска ключа в коробках. Помните, что первым был итеративный подход с использованием циклов? Согласно этому подходу Вы создаете стопку коробок для поиска, поэтому всегда знаете в каких коробках вы еще не искали.



Но в рекурсивном подходе нет стопки. Так как тогда алгоритм понимает в какой коробке следует искать? Ответ: «Стопка коробок» сохраняется в стеке. Формируется стек из наполовину выполненных обращений к функции, каждое из которых содержит свой наполовину выполненный список из коробок для просмотра. Стек следит за стопкой коробок для Вас!


И так, спасибо рекурсии, Вы наконец смогли найти свой ключ и взять рубашку!



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



Заключение от автора


Надеюсь, что статья внесла немного больше ясности в Ваше понимание рекурсии в программировании. Основой для статьи послужил урок в моем новом видео курсе от Manning Publications под названием «Algorithms in Motion». И курс и статься написаны по замечательной книге «Grokking Algorithms», автором которой является Adit Bhargava, кем и были нарисованы все эти замечательные иллюстрации.


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


От себя хочу добавить, что с интересом наблюдаю за статьями и видеоуроками Beau Carnes, и надеюсь что Вам тоже понравилась статья и в особенности эти действительно замечательные иллюстрации из книги A. Bhargav «Grokking Algorithms».

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 17

    +8
    Столько мути что бы донести такую простую вещь как рекурсия…
      –1
      if( post.match("что бы") &&
          post.slice(post.match("что бы").index+1).match(new Infinitive) ) {
          post.replace("что бы", "чтобы");
          if( post.match(/[а-я]\sчтобы/) ) {
              post.replace(" чтобы", ", чтобы");
          }
      }
        0

        "Что бы съесть такого, чтобы похудеть?"

        +1

        Да уж, да ещё и с блок-схемами, инфографикой и видюшкой на ютюбе.


        Помнится, нам на первом курсе препод сказал — вот рекурсия, вот пример, вот бест-практис — первой инструкцией писать выход из рекурсии — и, собственно, все.

        +10

        image

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

            Условно говоря да, чтобы не создавать заново вложенных мужиков при каждом распахивании. Но тут можно притянуть и такую аналогию: если мы создаем структуру (данных, элемент ГУИ и т.п.), то изначально вложенных элементов нет, мы их создаем по ходу. А если обходим готовую, то она уже есть в памяти. Хотя, если семантика ленивая (как в том же Haskell), то у нас может не быть ничего развернуто в памяти, а быть только правило-генератор вложенных дочерних элементов, вплоть до бесконечного количества мужиков :)

          +2
          Да это ж третья глава недавней книги «Грокаем алгоритмы».
          habrahabr.ru/company/piter/blog/323310
          Один в один.
            0

            ИМХО, проще понять и объяснить рекурсию на уровне ассемблера, чем на уровне какой-то "стопки коробок".


            Кроме того, автор немного недоговаривает, когда говорит что


            рекурсивные функции используют так называемый «Стек вызовов»

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


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


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

              +1
              У меня уже накопился некоторый опыт написания программ на Си++ и даже на чистом Си писал модули для ядра и я вот хочу сказать, что ничего, я повторюсь, НИЧЕГО нельзя объяснять новичку «на уровне ассемблера».

              Я понимаю, что тут наверное куча олдфагов, которые повидали дерьма с этими ассемблерами, но вот я начал программировать году эдак в 2011, когда слово ассемблер уже звучало очень страшно и абсолютно ненужно)) Я познакомился с ним всего около года назад, и до этого не чувствовал никакого дискомфорта. Думаю для тех, кто только начинает программировать на чём-то отличном от чистого Си (даже на С++), ассемблер — это то, с чем они познакомятся последним и правильно сделают.

              Рекурсия хорошо описывается математически и не надо быть гением, чтобы это понять.
                +1
                Рекурсия хорошо описывается математически и не надо быть гением, чтобы это понять.

                Рекурсия как явление в целом, бесспорно. Но автор затрагивает такое понятие как "стек вызовов", которое не очень-то старается объяснить. Также замалчивает что рекурсивная функция не может выполняться бесконечно (в отличие от цикла), потому что произойдет переполнение стека у исполняющего потока.


                Возможно такое объяснение подойдет для совсем новичков, но тогда возможно и не стоило приплетать сюда низкоуровневые понятия. То есть, на мой взгляд, получилось "ни рыба ни мясо".

                +3
                Я думаю, что вокруг видео и была запилена вся статья. Просмотры, лайки, и вот это всё. Хабр пока еще не скатился в омерзительный формат «видеопостов», но идет к этому уверенными шагами.
                  +1

                  Для меня самым простым объяснением рекурсии был пример быстрой сортировки.
                  Также полезно понять принцип "разделяй и властвуй", который используется при решении подобных задач.

                  +2
                  Ждал наглядного объяснения хвостовой рекурсии и про приведение ее к циклу
                  +1
                  Чтобы понять рекурсию поймите сперва рекурсию…
                  А если по существу, то есть книга SICP (Structure and Interpretation of Computer Program). Рекомендую к прочтению любому! Весьма интересная книга
                    0
                    Я в SICP не понял про аппликативный и нормальный порядок вычисления, только понял, что у обоих есть свои достоинства и недостатки, и что оба используются. Чего не понял: зачем в одном языке поддержка обоих, и не связан ли порядок вычисления с ленивостью вычислений.

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

                  Самое читаемое