Посмотрите на красоту рекурсии с аналогией и, да, без факториала.

Кажется, что каждый учебник, когда-либо написанный по рекурсии, использует алгоритм факториала в качестве примера. Новичку может быть трудно понять, что такое рекурсия, когда вы видите ее только с одной стороны. В этой статье я покажу, как написать 13 базовых алгоритмов (те, которые используются в 13 базовых алгоритмах Coding Dojo), которые обычно решаются с помощью итерации цикла с использованием рекурсии. . Это действительно помогло мне лучше понять рекурсию. Кроме того, я попробую провести аналогию и приведу пример, где почти все согласятся с тем, что вам нужно использовать рекурсию. Здравствуйте, flatten. И да, прощай факториал, по крайней мере пока.

Несколько предупреждений. Насколько я понимаю, функциональное программирование — тема интересная, но и сложная. У многих программистов есть чувства по этому поводу, некоторые хорошие, некоторые плохие. Поскольку мой опыт ограничен, я не буду вдаваться в FP (здесь задействовано много понятий, таких как состояние, изменчивость, >оптимизация хвостового вызова, параллелизм и побочные эффекты.) Использование FP в реальном мире требует многих соображений, большинство из которых я недостаточно хорошо разбираюсь, поэтому я буду придерживаться мыслительного процесса и стилистической красоты рекурсивного программирования. парадигма. Определенно есть кривая обучения, но понимание того, как рекурсивно писать алгоритмы, действительно расширит ваше понимание программирования (по крайней мере, для меня), и да, это тоже очень весело!

Помните: всегда убедитесь, что у вас есть базовый/стоп случай (условие), иначе вы получите сообщение об ошибке "достигнут максимальный стек вызовов".

Сначала несколько основных 13, затем аналогия (только что разобрался, как сделать ссылку на абзац :).

1. Получите от 1 до 255

Напишите функцию, которая возвращает массив со всеми числами от 1 до 255. В этом упражнении вы можете использовать функцию push().

2. Получить даже 1-10

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

3. Замените отрицательные числа на 0 (или на любое другое по вашему выбору)

Напишите функцию, которая изменяет любое отрицательное значение в массиве на 0.

(Больше основных 13 уже в пути….)

Аналогия без ручки

Вот небольшая аналогия, которую я придумал (не каламбур). Это далеко не идеально и, возможно, немного глупо, но мне помогло.

На дворе 1998 год, и вы звоните своей подруге Джен, чтобы спросить у нее номер телефона Майка. Она быстро находит свою контактную книгу и выдает вам номер. Джен очень организована, у нее всегда под рукой книга, а у тебя не очень. Вы быстро понимаете, что у вас нет ручки, чтобы написать номер Майка, поэтому вы говорите Джен, чтобы она подождала, пока вы кричите Сэму в соседней комнате, чтобы он запомнил этот номер для вас. Сэм повторяет номер снова и снова, чтобы сохранить его свежим, и когда вы кладете трубку с Джен, вы просите Сэма повторить вам номер и продолжаете звонить Майку. Я устал думать об этом.

Перенесемся в 2017 год. Мы все пользуемся смартфонами, и проблема отсутствия пера уже в прошлом.

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

Сэм (человек, который помнит мой номер) подобен переменной «i» в цикле for. Это внешний контейнер, который отслеживает некоторые данные для меня. А что, если я смогу просто избавиться от Сэма (мы любим тебя, Сэм, но ты должен уйти) и отслеживать наши собственные данные, просто передав их в новый вызов? Довольно круто, нет? (Я думаю, что слова состояниеиизменчивость должны быть в этом абзаце, но я еще не совсем там. ;)

Свести вложенный массив

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

var flattened = [];
function flatten(a, i) {
    if(a.length > i) {
        if(Array.isArray(a[i]))
            flatten(a[i], 0);
        else
            flattened.push(a[i]);
        flatten(a, i + 1);
    }
}

flatten([[0, 1], [2, 3], [4, 5]], 0);
console.log(flattened);
//courtesy of stackOverflow Adam https://stackoverflow.com/users/4491066/adam

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

Каждое утро в Coding Dojo мы тратим час на алгоритмы. Эта статья была вдохновлена ​​рекурсивными алгоритмами последних недель. Я надеялся, что, написав о теме, это поможет укрепить мое понимание. Это определенно помогло мне, и я надеюсь, что это помогло и вам.

Вы можете следить за моим путешествием по программированию здесь.

Спасибо за чтение!