Рекурсия

Визуализация рекурсивного процесса

https://goo.gl/gWCcgm

Представляем функции

  • Можно представить функции как чёрные коробки: коробка забирает объект, производит внутри какие-то действия, а потом выплёвывает что-то новое
    • Некоторые функции ничего не забирают (не принимают аргументы), некоторые вообще ничего не делают (они пустые), некоторые не возвращают значения.
    • Наш surfaceAreaCalculator принимает один аргумент (radius), вычисляет площадь поверхности и возвращает результат этого вычисления.
  • Функции могут вызывать другие функции
  • surfaceAreaCalculatorможет вызывать функцию square, чтобы получить радиус, возведённый в квадрат, вместо того, чтобы умножать радиус на радиус.
  • Мы пишем функции, чтобы облегчить жизнь:
    • такой код легче понимать
    • функции могут переиспользоваться несколько раз

Сравните:

const surfaceOfMars = surfaceAreaCalculator(3390);  // это "ЧТО", в таком виде легче понять суть
const surfaceOfMars = 4 * 3.14 * 3390 * 3390;       // это "КАК"

Две функции вместе:

const surfaceAreaCalculator = (radius) => {
  return 4 * 3.14 * square(radius);
}

const square = (num) => {
  return num * num;
}

Функции, которые вызывают сами себя

  • Определение функции — это описание коробки
  • Оригинал коробки формируется при вызове функции
  • Когда функция вызывает сама себя, создаётся новая идентичная коробка

Перестановки:

  • Количество способов перестановки n объектов равно n! (permutations)
  • n! определяется таким способом: если n = 1, то n! = 1; если n > 0, то n! = n * (n-1)!

Функция, вычисляющая факториал:

const factorial = (n) => {
  if (n === 1) {
    return 1;
  }
  else {
    return n * factorial(n-1);
  }
}

const answer = factorial(3);

Требования рекурсии

  1. Простой базовый случай или терминальный сценарий. Простыми словами, когда остановиться. В нашем примере это была 1: мы остановили вычисление факториала, когда достигли 1.
  2. Правило двигаться по рекурсии, углубляться. В нашем случае, это было n * factorial(n-1).

Ожидание умножения

Ничего не умножается, пока мы спускаемся к базовому случаюfactorial(1). Затем мы начинаем подниматься обратно, по одному шагу.

factorial(3);
3 * factorial(2);
3 * 2 * factorial(1);
3 * 2 * 1;
3 * 2;
6;

Примечание

Заметьте, что 0! это 1, а простой базовый случай для n! это 0! В этом уроке мы пропустили такой случай, чтобы сократить рекурсию на один вызов и на одну коробку, поскольку 1 * 1 — это, в любом случае — 1.

Просто ради забавы

У программистов есть одна шутка: "Чтобы понять рекурсию, нужно понять рекурсию". Google, кажется, любит такие шутки. Попробуйте погуглить "рекурсия" и зацените верхний результат поиска ;-)

Рекомендуем посмотреть

Опциональный текст

Опциональные видео


Упражнение

Реализуйте (с использованием рекурсивного процесса) функциюsequenceSum, которая находит сумму последовательности целых чисел. Последовательность задается двумя значениями:begin- начало последовательности,end- конец последовательности. Например:begin = 2иend = 6дают нам такую последовательность2, 3, 4, 5, 6. Сумма такой последовательности будет:20.

import sequenceSum from './sequenceSum';

sequenceSum(1, 5); // 1 + 2 + 3 + 4 + 5 = 15
sequenceSum(4, 10); // 4 + 5 + 6 + 7 + 8 + 9 + 10 = 49
sequenceSum(-3, 2); // (-3) + (-2) + (-1) + 0 + 1 + 2 = -3

Подсказки

  • Последовательность, в которойbegin > end, не содержит ни одного числа, т.е. является "пустой". Вычислить сумму чисел такой последовательности не представляется возможным, в этом случае возвращаемNaN
  • Сумма чисел последовательности, в которойbegin === end, равнаbegin(илиend)
// NaN (т.к. это "пустая" последовательность)
sequenceSum(7, 2);

// 0 (т.к. это единственное число, входящее в последовательность)
sequenceSum(0, 0);
// 6 (т.к. это единственное число, входящее в последовательность)
sequenceSum(6, 6);

/

//

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

/

const sequenceSum = (begin, end) => {
  if (begin > end) {
      return NaN;
    } else if (begin === end) {
      return begin;
    }
    return begin + sequenceSum(begin + 1, end);
};

results matching ""

    No results matching ""