2

На фрикодкемп есть задание преобразования цикла в рекурсию. Задача: перемножить n первых элементов массива arr

Пример решения задания через циклы:

function multiply(arr, n) {
    let product = 1;
    for (let i = 0; i < n; i++) {
      product *= arr[i];
    }
    return product;
  }

А это решение через рекурсию:

function multiply(arr, n) {
    if (n <= 0) {
      return 1;
    } else {
      return multiply(arr, n - 1) * arr[n - 1];
    }
  }

Не совсем понять принцип работы данной функции(через рекурсию), может кто-нибудь может пошагово объяснить, что происходит?

4

1 ответ 1

5

Смысл рекурсии в вызове в теле функции самой себя для вычисления повторяющихся вычислений.

В данном случае Вы должны перемножить первые n элементов массива.

Из того что использовать циклы Вы не можете и Вам нужно использовать рекурсию следует:

  1. За один вызов вы можете выполнить одну операцию умножения
  2. Вы постепенно должны перемещаться от одного края интервала до другого чтобы перебрать все элементы
  3. Т.к. Вы должны перемещаться по массиву - у Вас должен быть курсор отвечающий за смещение внутри массива
  4. Итоговый результат должен будет аккумулироваться
  5. Результат перемноженных ранее элементов должен умножаться на текущий элемент

Рассмотрим код:

function multiply(arr, n) {
    if (n <= 0) {
      return 1;
    } else {
      return multiply(arr, n - 1) * arr[n - 1];
    }
}
function multiply(arr, n)

Тут все банально: принимаем на вход массив и кол-во элементов


if (n <= 0) {

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


return 1;

Это результат, возвращаемый при выходе из рекурсии.
Данный результат никак не должен повлиять на общий результат и т.к. мы перемножаем все элементы, то единственным возможным (в данной реализации) вариантом является единица.


} else {

Собственно дальше мы переходим в блок в котором будут вложенные вызовы рекурсии.
то бишь - это основное тело рекурсии


return multiply(arr, n - 1) * arr[n - 1];

Вот и оно:
Здесь мы берем крайний правый элемент нашего интервала (arr[n - 1]) и умножаем его на результат перемножения интервала, в котором элементов на 1 меньше (multiply(arr, n - 1)).

То есть мы взяли и выдернули из интервала последний элемент и умножили его на результат перемножения оставшегося интервала.
И дальше это будет продолжаться по кругу, пока мы не пройдемся по всем элемента интервала и не дойдем до конца - до условия выхода из рекурсии.

К тому времени мы перемножим между собой все элементы интервала


Можно на примере:

 шаг 1: multiply([1,2,3,4,5,6,7,8])
 шаг 2: multiply([1,2,3,4,5,6,7]) * 8
 шаг 3: multiply([1,2,3,4,5,6]) * 7 * 8
 шаг 4: multiply([1,2,3,4,5]) * 6 * 7 * 8
 шаг 5: multiply([1,2,3,4]) * 5 * 6 * 7 * 8
 шаг 6: multiply([1,2,3]) * 4 * 5 * 6 * 7 * 8
 шаг 7: multiply([1,2]) * 3 * 4 * 5 * 6 * 7 * 8
 шаг 8: multiply([1]) * 2 * 3 * 4 * 5 * 6 * 7 * 8
 шаг 9:               1 * 2 * 3 * 4 * 5 * 6 * 7 * 8

 итог: мы постепенно, вызов за вызовом, в одну цепочу 
       перемножили все элементы нужного интервала

Замечание: в примере для простоты и наглядности использован псевдокод.


Чисто математически рекурсия создает у нас что-то такое:

9 * ( 8 * ( 7 * ( 6 * ( 5 * ( 4 * ( 3 * ( 2 * ( 1 ) ) ) ) ) ) ) )

Соответсвенно: каждый новый вызов соответствует открытию новой скобки

9 * ( 
      8 * ( 
            7 * ( 
                  6 * (
                        5 * (
                              4 * (
                                    3 * (
                                          2 * ( 
                                                1
                                              )
                                        )
                                  )
                            )
                      )
                ) 
          )
     )

И когда мы доходим до конца(условие выхода из рекурсии) все выражение схлопывается и мы получаем результат


Иллюстрация подобной рекурсии в дебаггере
Здесь я перемножил первые 5 элементов данного списка

  • Для иллюстрации интервала, с которым на данным момент ведется работа я ввел переменную real_range - можете следить за тем как она изменяется от вывоза к вызову.
  • Для иллюстрации результата я ввел временную переменную temp
  • Собственно когда данный список заканчивается - мы попадаем на условие выхода из функции и все наши вызовы схлопываются и происходит обратный процесс наша функция начинает с самого конца возвращать результаты и мы начинаим их перемножать в обратном порядке.
  • также можете наблюдать как callstack (стек вызовов функции) сначала увеличивается, достигает своего максимума при условии выхода из рекурсии, после чего начинает уменьшаться до тех пор пока изначальная функция не вернет результат
  • можете заметить что пока мы не дошли до конца списка - результатов никаких у нас не было(переменная temp), но после того как мы достигли условия выхода из рекурсии - она начала сворачиваться и мы начали постепенно получать результаты(temp начал отображать результаты перемножения)

введите сюда описание изображения

Пример по просьбам трудящихся - на python
(Могу на JS или еще чем предоставить если нужно)


Хвостовая рекурсия:

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

И в таких языках для итерации списков частенько используется хвостовая рекурсия (а что им еще делать? нужно же как-то выкручиваться)

Что это такое?

Список делится на две части:

  • голова (первый элемент списка)
  • хвост (оставшиеся элементы списка)
голова | хвост
     ↓ |    ↓
     _ | _____________
    [1,| 2, 3, 4, 5, 6]

И зачастую в этих языках у списков и коллекций имеются соответствующие методы или свойства head() и tail() (хотя могут быть и просто операторы, которые нигде больше в программировании не используются)

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

// ПСЕВДОКОД  ↓

function multiply(list){
    return list.head() * multiply(list.tail())
}

Так выглядит чуть приятнее и понятнее чем в нашем варианте.

Хотя по сути мы до этого делали примерно то же самое в вышеупомянутом коде.
Только у нас нет встроенных метод head() и tail()
Хотя с другой стороны никто не мешает их добавить - в понятности скрипт только выиграет.


ну и на последок:

Все тоже самое можно было бы записать гораздо короче:

function multiply(arr, n) {
    return n <= 0 ? 1 : multiply(arr, n - 1) * arr[n - 1];
}

По сути это абсолютно все тоже самое, только записанное в одну строку(я про тело функции)

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.