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

Что это такое

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

Понимание компромиссов

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

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

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

Примеры

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

Пример 1: Напишите функцию, которая принимает основание и показатель степени и возвращает степень основания степени. Не беспокойтесь об отрицательных основаниях или показателях степени.

Iterative Loop Solution
function power(base, exp){
  let result = 1
  if(exp === 0) return result
  while(exp > 0){
   result *= base
   exp--
  }
  return result
}
Recursive Solution
function power(base, exp){
  if(exp === 0) return 1
  return base * power(base, exp - 1)
}
power(2, 0) // 1
power(2, 2) // 4
power(2, 4) // 16

Пример 2: Напишите функцию, которая принимает число и возвращает N-е число в последовательности Фибоначчи. Последовательность Фибоначчи - это последовательность целых чисел (1,1,2,3,5,8,…), которая начинается с 1 и 1 и продолжается, где каждое последующее число является суммой двух предыдущих чисел.

Iterative Loop Solution
function fib(num){
  let n = 1
  let arr = [1,1]
  let i = 1
  while(i<num-1){
    n = arr[i] + arr[i-1]
    arr.push(n)
    i++
  }
  return n
}
Recursive Solution
function fib(num){
  if(num < 3) return 1
  return fib(num - 1) + fib(num - 2)
}
fib(4) // 3
fib(8) // 21
fib(28) // 317811

Пример 3. Напишите функцию, которая принимает аргумент строки и возвращает истину, если это палиндром (читает то же вперед и назад), и ложь, если это не так.

Iterative Loop Solution
function isPalindrome(str){
  let arr = str.split("")
  let newArr = []
  for(var ele of arr){
    newArr.unshift(ele)
  }
  return newArr.join("")===str
}
Recursive Solution
function isPalindrome(str){
  if(str.length<=1) return true
  if(str.length===2) return(str[0]===str[1])
  if(str[0]===str.slice(-1)) return isPalindrome(str.slice(1, -1))
  return false
}
isPalindrome('righton') // false
isPalindrome('croatia') // false
isPalindrome('biggib') // true
isPalindrome('amanaplanacanalpanama') // true
isPalindrome('recursionnoisrucer') // true

Заключение

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