Введение в рекурсию

Введение в рекурсию

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

Что такое рекурсия?

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

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

function recursivelyDeincrement(n) {
  // prevent the loop from going infinite if no number is given
  if(isNaN(n)) {
    return 0
  }
  if(n === 0) {
    console.log("We have reached 0!!!")
  } else {
    console.log(`Currently logging ${n}`)
    return recursivelyDeincrement(n - 1)
  }
}
recursivelyDeincrement(10)
=> Currently logging 10!
=> Currently logging 9!
=> Currently logging 8!
=> Currently logging 7!
=> Currently logging 6!
=> Currently logging 5!
=> Currently logging 4!
=> Currently logging 3!
=> Currently logging 2!
=> Currently logging 1!
=> We have reached 0!!!

Итак, вы можете видеть здесь, что deincrementRecursively(n) имеет рекурсивный вызов и базовый случай. После запуска функции будет выполнена проверка текущего значения n. Если n больше 0, мы будем рекурсивно вызывать deincrementRecursively(), передавая n — 1 в качестве аргумента (рекурсивный вызов). В противном случае, если n равно 0, мы вернем не вызов функции, а значение, которое остановит зацикливание функции (базовый случай).

Примеры рекурсивных функций

двесуммы()

Давайте взглянем на часто встречающуюся функцию twoSum() и реализуем рекурсивное решение. Вот определение twoSum(), которое вы, вероятно, видели раньше:

function twoSum(num1, num2) {
  return num1 + num2
}
twoSum(5, 10)
=> 15

Достаточно просто? twoSum(num1, num2) довольно прост — он берет два числа, суммирует их и возвращает это значение. Если бы мы написали это рекурсивно, мы могли бы сделать это так:

function recursiveTwoSum(num1, num2) {
  if(num1 > 0) {
    // recursive call
    return recursiveTwoSum(num1 - 1, num2 + 1)
  } else {
    // base case
    return num2
  }
}

Подобно функции recursivelyDeincrement(n), recursiveTwoSum(num1, num2) возвращает либо рекурсивный вызов, либо базовый случай соответственно.

уменьшать()

Давайте попробуем еще раз, определив рекурсивный метод reduce(). Помните, что reduce() берет коллекцию и объединяет элементы этой коллекции с начальным значением:

function reduce(array, combine, start) {
  var current = start
  for (var i = 0; i < array.length; i++)
    current = combine(current, array[i])
  return current
}
reduce([1,2,3,4], function(a,b) {
  return a + b
}, 0)
=> 10
reduce([1,2,3,4], function(a,b) {
  return a + b
}, 5)
=> 15

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

function recursivelyReduce(arr, start) {
  if(arr.length === 1) {
    return arr[0] + start
  } else {
    arr[0] += arr.pop()
    return recursivelyReduce(arr, start)
  }
}
recursivelyReduce([1,2,3,4], 0)
=> 10
recursivelyReduce([1,2,3,4], 5)
=> 15

Вывод

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

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