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

Важной особенностью языка JavaScript является то, что функция может вызывать не только другие функции, но и сама себя. Такие функции называются рекурсивными (recursive function). Применение рекурсивных функций, во многих случаях, позволяет писать компактный код вместо сложных вложенных циклов.

В качестве одного из примеров можно привести расчет факториалов. Обозначается факториал восклицательным знаком "!" и вычисляется следующим образом:

N! = N * (N-1) * (N-2) * ... * 1.

Так, в соответствии с этим определением, мы имеем 5! = 5*4*3*2*1, т.е. 120. Напомним также, что значение 0! определяется равным 1, а факториалы отрицательных чисел не определены.

В следующем примере показано, как подсчитать факториалы итерационно, т. е. с помощью цикла while, в котором вычисляется результат:

Выполнить код »

Этот пример можно легко преобразовать в рекурсию. Внимательнее изучив формулу факториала, мы можем прийти к выводу, что:

N! = N * (N-1)!

Итак, мы определили факториал через сам факториал! На первый взгляд, такое определение совершенно бесполезно, ведь неизвестное значение определяется через опять же неизвестное значение, и мы получаем бесконечный цикл. Но на самом деле это не так, потому что факториал N! определяется через факториал (N-1)!. Таким образом, нахождение функции сводится к вычислению той же неизвестной функции, но от другого аргумента, на единицу меньшего, чем исходный. Отсюда следует, что каждая следующая задача будет решаться чуть легче предыдущей.

Для того, чтобы окончательно разорвать замкнутый круг дополним рекурсивное определение N! = N * (N-1)! еще одним, которое будет служить для остановки процесса:

1! = 1

Попробуем теперь вычислить значение 5!, несколько раз применив правило N! = N * (N-1)! и однократно правило 1! = 1:

5! = 5 * 4! = 5 * 4 * 3! = 5 * 4 * 3 * 2! = 5 * 4 * 3 * 2 * 1! = 5 * 4 * 3 * 2 * 1

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

Выполнить код »

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

А теперь давайте разберём как же работает наша функция factorial().

Когда factorial() вызывается с аргументом 1, функция возвращает 1. В противном случае она возвращает произведение num * factorial(num - 1). Для вычисления этого значения factorial() вызывается с num - 1. Это происходит, пока num не станет равно 1.

Например, при передаче числа 5, у нас образуется следующая цепочка вызовов:

1↓ var result = 5 * factorial(4);              ←  // 120
2↓ var result = 5 * 4 * factorial(3);          ↑
3↓ var result = 5 * 4 * 3 * factorial(2);      ↑
4↓ var result = 5 * 4 * 3 * 2 * factorial(1);  ↑
5→ var result = 5 * 4 * 3 * 2 * 1;             ↑      

Ничего не умножается, пока мы спускаемся к базовому случаю factorial(1). Затем мы начинаем подниматься обратно, по одному шагу.

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

Общее количество вложенных вызовов называют глубиной рекурсии. В случае с factorial(), всего будет num вызовов. Максимальная глубина рекурсии в браузерах ограничена 10 000 рекурсивных вызовов.

Когда функция вызывает сама себя, в стеке выделяется место для хранения новых копий локальных переменных и параметров. Код функции работает с данными переменными. Большое количество рекурсивных вызовов в функции может привести к переполнению стека. Если это произойдет, то возникнет ошибка - переполнение стека.

Рассмотрим другой пример – определение чисел Фибоначчи.

Числа Фибоначчи – это ряд чисел, в котором каждое последующее число равно сумме двух предыдущих: первые два числа равны 1, затем 2(1+1), затем 3(1+2), 5(2+3) и так далее 1, 1, 2, 3, 5, 8, 13 и т.д.

Для вычисления Fn n-го числа Фибоначчи воспользуемся рекуррентным соотношением:

  • F1 = 1
  • F2 = 1
  • Fn = Fn-1 + Fn-2, n > 2

Если напрямую написать решение этой задачи, переписав рекурсию в код, то получим очень простую реализацию, повторяющую математическое определение:

Выполнить код »

К недостаткам применения рекурсии, в данном случае, относятся экспоненциальное время выполнения и переполнение стека. При больших значениях n функция будет работать очень медленно. Например, fib(49) уже будет вычисляться так долго, что возможно вы решите перезагрузить браузер.

Рекурсивный вызов функции fib(6) можно представить следующим образом:

1↓ fib(6) = fib(5) + fib(4)  
2↓ fib(5) = fib(4) + fib(3)  
3↓ fib(4) = fib(3) + fib(2)  
4↓ fib(3) = fib(2) + fib(1)
5↓ fib(2) = fib(1) + fib(0)
6↓ fib(1) = 1
7↓ fib(0) = 0    

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

                                       6
                  ------------------------------------------
                 |                                          |
                 4                     +                    5
        -------------------                        -------------------
       |                   |                      |                   |
       2         +         3                      3        +          4
   ---------           ---------              ---------           ---------
  |         |         |         |            |         |          |        | 
  0    +    1         1    +    2            1   +     2          2   +    3
                              -----                  -----      -----    -----
                             |     |                |     |    |     |  |     | 
                             0  +  1                0  +  1    0  +  1  1  +  2
                                                                            ----- 
                                                                           |     |
                                                                           0  +  1

Как видите, ряд значений вычисляется много раз. Здесь видно, что, например, значение функции fib(2) будет вычисленно 5 раз! и, при этом, совершенно независимо друг от друга.

А теперь просуммируем результаты вычислений для левой ветки fib(4):

( 0 + 1 ) +  ( 1 + ( 0 + 1 ) ) == 3

Тоже самое, но для правой ветки fib(5):

( 1 + ( 0 + 1 ) + ( 0 + 1 ) +  ( 1 + ( 0 + 1 ) )) == 5

И, как результат: fib(5) == 8

Для определения чисел Фибоначчи лучше применять итерацию (цикл), чем рекурсию:

Выполнить код »

Решение основывается на том, что для вычисления следующего числа нужно помнить всего 2 предыдущих. Здесь цикл for начинается с i=3, так как первые два числа Фибоначчи заранее записаны в переменные var a = 1, b = 1. В каждом следующем шаге цикла цифры ряда Фибоначчи будут смещаться на одну вперед. Теперь b перемещается в а, с перемещается в b, а последующее число равно сумме двух предыдущих c = a + b. И так повторяем в цикле до тех пор, пока не получим нужное значение.

  • Рекурсия – это функция, которая сама вызывает себя, как правило, с другими аргументами.
  • Наилучшее применение рекурсии – это решение задач, для которых свойственна одна черта: решение задачи в целом сводится к решению подобной же задачи, но меньшей размерности и, следовательно, легче решаемой.
  • Рекурсия и итерация эквивалентны – это значит, что любой алгоритм, который можно реализовать рекурсивно, с таким же успехом может быть реализован и итеративно (через цикл), и наоборот.
  • Общее количество вложенных вызовов называют глубиной рекурсии. Максимальная глубина рекурсии в браузерах ограничена 10 000 рекурсивных вызовов.
  • Значение, на котором рекурсия заканчивается, называют базовый случай или терминальный сценарий.
  • Большое количество рекурсивных вызовов в функции может привести к переполнению стека. Поскольку местом для хранения параметров и локальных переменных функции является стек, а каждый новый вызов создает новую копию переменных, пространство стека может исчерпаться.

  • Вывод чисел от 1 до n

    Дано натуральное число n. Выведите все числа от 1 до n. При решении задач на рекурсию в первую очередь нужно найти ответы на следующие вопросы: Какой базовый случай в задаче? Какой шаг рекурсии или рекурсивное условие можно здесь применить?

    Показать решение

    Решение:

    Выполнить код »
  • Вывод чисел от a до b

    Даны два целых числа a и b. Выведите все числа от a до b включительно, в порядке возрастания, если a < b, или в порядке убывания в противном случае.

    Показать решение

    Решение:

    Выполнить код »
  • Сумма цифр числа

    Дано натуральное число n. Вычислите сумму его цифр. При решении этой задачи используйте рекурсию.

    Показать решение

    Решение:

    Последняя цифра любого числа, обозначающая единицы, извлекается путем нахождения остатка от деления на 10: n % 10. Её мы прибавим к значению рекурсивной функции, которую вызываем уже без этой последней цифры числа. И так, пока у нас не останется одна цифра, т.е. n < 10.

    Выполнить код »
  • Цифры числа справа налево

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

    N = 89652 → 2 5 6 9 8
    
    Показать решение

    Решение:

    Выполнить код »
  • Цифры числа слева направо

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

    N = 89652 → 8 9 6 5 2
    
    Показать решение

    Решение:

    Выполнить код »
  • Вывести нечетные числа последовательности 0...N

    Дана последовательность натуральных чисел от N до 0. Напишите код, который запрашивает число N и выводит все нечетные числа из этой последовательности, сохраняя их порядок. Например:

    N = 8 → 7 5 3 1
    
    Показать решение

    Решение:

    Выполнить код »
  • Вывести число наоборот

    Дано число N. Выведите число, записанное теми же цифрами, но в противоположном порядке. Например:

    N = 854 → 458
    
    Показать решение

    Решение:

    Выполнить код »

Комментарии

пожелания к комментариям…
  • Приветствуются комментарии, соответствующие теме урока: вопросы, ответы, предложения.
  • Одну строчку кода оборачивайте в тег <code>, несколько строчек кода — в теги <pre><code>...ваш код...</code></pre>.
  • Допускаются ссылки на онлайн-песочницы (codepen, plnkr, JSBin и др.).