15.09.2020 08:21
aio350 9 1300 Источник


Доброго времени суток, друзья!

Прочитал на freeCodeCamp статью про рекурсию.

Для того, чтобы понять рекурсию, нужно сначала понять рекурсию. Чего?

Рекурсия — это когда функция вызывает сама себя. Уже лучше.

Пример из статьи: 

const counter = number => {
    // условие остановки рекурсии
    if (number === 0) {
        return
    }
    console.log(number)
    return counter(number - 1)
}
counter(5) // 5 4 3 2 1

Вот оно что… А почему нельзя перебрать элементы в цикле?

Например, так:

const counter2 = num => {
    while (num !== 0) {
        console.log(num)
        num--
    }
}
counter2(5) // 5 4 3 2 1

Ответа на данный вопрос статья не содержит. Видимо, так неинтересно.

Более того, в ней говорится о том, что рекурсия, как правило, менее производительна по сравнению с другими способами решения задачи.

Тем не менее, в статье предлагается два упражнения, которые мне захотелось решить. Делюсь с вами результатами и приглашаю внести свою лепту.

Задачи простые, если не считать того, что их надо решить с помощью рекурсии.

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

Задача номер раз


Реализуйте функцию, принимающую строку и инвертирующую ее. Например, строка «JavaScript» должна стать строкой «tpircSavaJ».

Рекурсия
Обычная функция:

function invert(string) {
    const lastIndex = string.length - 1
    if (lastIndex > 0) {
        return string[lastIndex] + invert(string.slice(0, lastIndex))
    } else {
        return string
    }
}

const str = 'JavaScript'

console.log(invert(str)) // tpircSavaJ

Стрелочная функция + тернарный оператор:

const invert2 = (str, i = str.length - 1) => (i > 0) ? str[i] + invert2(str.slice(0, i)) : str

console.log(invert2(str)) // tpircSavaJ

Стрелочная функция + тернарный оператор + деструктуризация:

const invert3 = ([firstLetter, ...str]) => firstLetter ? invert3(str) + firstLetter : ''

console.log(invert3(str)) // tpircSavaJ


Нерекурсия
Стрелочная функция:

const invert4 = str => str.split('').reverse().join('')

console.log(invert4(str)) // tpircSavaJ

Стрелочная функция + деструктуризация:

const invert5 = str => [...str].reverse().join('')

console.log(invert5(str)) // tpircSavaJ


Задача номер два


Реализуйте функцию, принимающую строку и символ и возвращающую количество символов в строке. Например, если мы передаем «JavaScript» и «a», то должны получить 2 (в строке «JavaScript» две буквы «a»).

Рекурсия
У меня не получилось решить эту задачу также изящно, как предыдущую. Если у вас получится, прошу поделиться в комментариях.

Обычная функция:

function count(string, letter) {
    if (string.length > 0) {
        if (string[0] === letter) {
            return 1 + count(string.slice(1), letter)
        } else {
            return count(string.slice(1), letter)
        }
    } else {
        return 0
    }
}

console.log(count(str, 'a')) // 2

Стрелочная функция + тернарный оператор:

const count2 = (
    str,
    l,
    str2 = str.slice(1)
) => (str.length === 0) ? 0 : (str[0] === l) ? 1 + count2(str2, l) : count2(str2, l)

console.log(count2(str, 'a')) // 2


Нерекурсия
Стрелочная функция:

const count3 = (str, l, n = 0) => {
    str
        // .toLowerCase()
        .split('')
        .map(lt => {
            if (lt === l) {
                n++
            }
        })
    return n
}

console.log(count3(str, 'a')) // 2

Еще одна стрелочная функция:

const count4 = (str, l) => str.toLowerCase().split(l).length - 1

console.log(count4(str, 'a')) // 2

Стрелочная функция + деструктуризация:

const count5 = (str, l) => [...str.toLowerCase()].filter(lt => lt === l).length || 0

console.log(count5(str, 'a')) // 2

Стрелочная функция + регулярное выражение:

const count6 = (str, l) => {
    const m = str.match(new RegExp(l, 'gi'))
    return m ? m.length : 0
}

console.log(count6(str, 'a')) // 2


Немного отсебятины


Можно придумать еще парочку задач со строками, но уже без рекурсии.

Как «капитализировать» строку, т.е. сделать первую букву заглавной?

const capWord = str => `${str[0].toUpperCase()}${str.slice(1)}`

console.log(capWord('hello')) // Hello

Что, если строка состоит из нескольких слов?

const capWords = str =>
    str.split(' ')
    // используем предыдущую функцию
    .map(i => capWord(i))
    .join(' ')

console.log(capWords('hello, world')) // Hello, World

Как привести строку к camel case?

const toCamelCase = str => str.split(' ').reduce((acc, cur) => acc + capWord(cur))

console.log(toCamelCase('camel case hello world')) // camelCaseHelloWorld

Как капитализировать слова в строке с помощью регулярного выражения?

const capWithRegex = str =>
    str.replace(
        // регулярка зависит от строки, для кириллицы - /[а-яё]\S+/gi
        /\w+\S+/gi,
        txt => `${txt[0].toUpperCase()}${txt.slice(1).toLowerCase()}`
    )

console.log(capWithRegex('pRima, alTera, triEra')) // Prima, Altera, Triera

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

Рекурсивный образ мышления (назовем его так) показался мне непривычным и неудобным, каким-то, выражаясь словами героев фильма «Довод», инвертированным: ехали медведи на велосипеде, а за ними кот задом наперед. И только я подумал о том, что не вижу объективных причин целенаправленно формировать у себя такое мышление, как вспомнил об алгоритмах, ведь многие из них пропитаны рекурсией. Все-таки придется инвертироваться.

А что вы думаете о рекурсии?