Я часто читал о том, что окончил учебный курс по разработке программного обеспечения 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
Заключение
Выбор между использованием итеративного цикла и рекурсивной функции будет зависеть от того, на каком языке программирования вы пишете код и какую проблему вы пытаетесь решить. Надеюсь, это руководство было полезно для понимания этой матрицы решений. Удачного кодирования!