Нет ничего более яркого и полезного для интервью JavaScript, чем рекурсия.

Если вы просто хотите быть впечатляющими с рекурсией в JavaScript, вот несколько примеров полуреального мира (тип технического теста).

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

Итак, рекурсия состоит из нескольких шагов.

В этой публикации мы обсудим:

• ? Рекурсия для обертывания последовательных запросов HTTP
• ? Подсчитайте количество символов

Примеры этой публикации также есть на ObervableHQ, который является чрезвычайно крутым инструментом, который позволяет создавать блокноты JavaScript:

Скажем, вам нужно получить несколько страниц из REST API, и вы вынуждены использовать родной модуль HTTPS (пример здесь). В этой ситуации мы будем получать комментарии по API Reddit.

С помощью этого API:

• если в одном ответе содержится больше комментариев, он вернет an after поле в данных. Это можно использовать как параметр запроса в запросе, чтобы получить следующий кусок комментариев.
• если больше нет комментариев, after будет фальшивым

Это определяет наши конечные и рекурсивные случаи. Мы получаем данные из API Reddit, а затем:

• after является фальшивым → прекращение делавернуть данные
• after определяется → рекурсивный случайпередайте его, чтобы получить следующую страницу, а также данные, возвращенные по текущему вызову

Один из используемых здесь трюков — это передача пустого data массив в recursiveCommentFetch функция с первого прохода Это позволяет нам продолжать вводить все большее и большее значение во время каждого рекурсивного вызова. Мы можем решить полный набор при прекращении дела.

const fetch = require('node-fetch');
const user="hugo__df";
function makeRedditCommentUrl(user, queryParams) {
  return `
    Object.entries(queryParams)
      .filter(([k, v]) => Boolean(v))
      .map(
        ([k, v]) => `${k}=${v}`
      ).join('&')
  }`;
}
function recursiveCommentFetch(user, data = [], { after, limit = 100 } = {}) {
  const url = makeRedditCommentUrl(user, { after, limit });
  return fetch(url)
    .then(res => res.json())
    .then(res => {
      const { after, children } = res.data;
      const newData = [...data, ...children];
      if (after) {
        // recursive case, there's a way to fetch more comments
        return recurseCommentFetch(user, newData, { after });
      }
      // base or terminating case
      return newData;
    });
}
recursiveCommentFetch(user)
  .then(comments => console.log(comments));

Я ознакомился с этим API, создав такую ​​визуализацию взносов Reddit (в стиле графика взносов GitHub). Смотрите здесь. Версия блога также доступна.

Когда вопрос звучит примерно так: «при входных данных верните объект, содержащий количество раз каждый символ присутствующий во входных данных», вы будете использовать этот метод.

Здесь есть демонстрация в прямом эфире.

Завершающий и рекурсивный регистр не сразу очевиден, поэтому здесь есть несколько шагов:

1. понимая, что входные данные можно привести к строке, что может быть .split в массив (т.е. большинство произвольных введенных данных можно превратить в массив).
2. знать, как делать рекурсию через массив. Это, пожалуй, одна из самых простых/распространенных вещей для повторного просмотра. Но нужно увидеть это пару раз, чтобы начать чувствовать себя удобно делать это.

Это дает нам такую ​​ситуацию для рекурсивной функции:

• список/массив символов пуст → прекращение делавернуть characterToCount карта
• список/массив символов не пуст → рекурсивный случайобновление characterToCountMap путем увеличения/инициализации ввода текущего символа. Вызвать рекурсивную функцию с обновленной картой и остальным списком/массивом.

Я написал более полный пост: Рекурсия в JavaScript с ES6, деструктуризация и отдых/распространение, в котором подробнее (примеры и методы) рассказывается о том, как мы можем повторять списки (массивы) в ES6 JavaScript. Это объясняет такие вещи, как [firstCharacter, ...rest] обозначение.

function recurseCountCharacters(
  [firstCharacter, ...rest],
  characterToCountMap = {}
) {
  const currentCharacterCount = characterToCountMap[firstCharacter] || 0;
  const newCharacterToCountMap = {
    ...characterToCountMap,
    [firstCharacter]: currentCharacterCount + 1
  };
  
  if (rest.length === 0) {
    // base/terminating case
    // -> nothing characters left in the string
    return newCharacterToCountMap;
  }
  // recursive case
  return recurseCountCharacters(rest, newCharacterToCountMap);
}
function countCharacters(input) {
  return recurseCountCharacters(String(input).split(''));  
}
console.log(countCharacters(1000000));
// { "0":6, "1": 1 }
console.log(countCharacters('some sentence'));
// { "s":2,"o":1,"m":1,"e":4," ":1,"n":2,"t":1,"c":1}

Вот как вы проходят интервью, используя рекурсию?, бегая вокруг этих игрушечных проблем.

Рекурсивные решения проблем интервью в конечном итоге выглядят более крутыми и чистыми, чем итерационные. Они приятны для интервьюера.

По любым вопросам вы можете связаться со мной на Twitter @hugo__df.

Получайте все сообщения недели раньше, чем кого-либо еще в вашем ящике: код с помощью информационного бюллетеня Hugo.