После того, как я не программировал несколько лет, я недавно начал переучивать его, будучи студентом Hack Reactor. Некоторые методы и идеи вернулись легче, чем другие, но одной из самых трудных для меня мыслей была рекурсия.

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

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

Вы уловили идею.

var digitalRoot = function(n) {
  //We'll problem-solve here.
};

Шаг 1. Определите «базовый случай», используя тривиальные данные.

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

В этом случае мы знаем, что наша функция digitalRoot примет целое число и выдаст целое число. Мы также знаем, что сумма цифр для однозначного числа… есть сама по себе. Если мы передадим 1 в нашу функцию, мы должны просто получить 1. Если мы передадим 2 в нашу функцию, мы должны просто получить 2. Давайте его псевдокодируем.

var digitalRoot = function(n) {
  // if n is a single-digit number
    // return n
};

Шаг 2: Определите рекурсивный случай.

Теперь, обращаясь к нашему базовому случаю, мы знаем, что: если n - любое число с более чем одной цифрой, нам нужно выполнить рекурсию. Но как именно как мы собираемся выполнять рекурсию и что мы собираемся передавать в функцию каждый раз, чтобы получить то, что мы хотим? Это сложная часть.

var digitalRoot = function(n) {
  // if n is a single-digit number
    // return n
  // else if n has more than one digit
    //recursion here
};

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

Шаг 3. Выполните простой ввод через рекурсивный регистр.

var digitalRoot = function(n) {
  // if n is a single-digit number
    // return n
  // else if n has more than one digit
    
  // digitalRoot(12) => 1+2 = 3
  // digitalRoot(40) => 4+0 = 4
  // digitalRoot(75) => 7+5 = 12 => digitalRoot(12) = 3
};

Надеюсь, именно здесь мы начнем выявлять закономерности. Написав это так, мы можем начать видеть, как это работает: каждый раз, когда n имеет две или более цифры, нам нужно вызвать digitalRoot по сумме цифр. Если мы сделаем это действительно явным, это будет выглядеть так:

var digitalRoot = function(n) {
  // if n is a single-digit number
    // return n
  // else if n has more than one digit
    //return digitalRoot(sum of n's digits)
// digitalRoot(12) => digitalRoot(3) = 3
// digitalRoot(40) => digitalRoot(4) = 4
// digitalRoot(75) => digitalRoot(12) => digitalRoot(3) = 3    
};

Шаг 4: Учитывайте любые побочные ограничения.

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

var digitalRoot = function(n) {
  // if n is a single-digit number
    // return n
  // else if n has more than one digit    
    //make array of digits
    //return digitalRoot(sum of n's digits)
};

Шаг 5: Преобразуйте псевдокод в реальный код.

var digitalRoot = function(n) {
  if (n < 10) {
    return n;
  }
/*converts to a string, then to an array of chars, then to an
  array of integers using the Number wrapper object*/
  var str= n.toString();
  var stringDigits = str.split("");
  var digits = stringDigits.map(Number);
  var sum = digits.reduce((a, b) => a + b);
  return digitalRoot(sum);
};

Мы сделали это! Может быть, нам удастся реорганизовать это, чтобы сделать его более лаконичным.

var digitalRoot = function(n) {
  if (n < 10) {
    return n;
  }
  var digits = n.toString().split("").map(Number)
  var sum = digits.reduce((a, b) => a + b);
  return digitalRoot(sum);
};

И еще более кратко. . .

function digitalRoot(n) {
  return n < 10 ? n : digitalRoot(n.toString().split("").map(Number).reduce((a, b) => a + b));
}

Хороший.

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