Эрудит Блез Паскаль представил треугольник, построенный из чисел. Треугольник Паскаля - как его обычно называют, несмотря на тот факт, что его открытие предшествовало Паскалю на столетия, - обладает тем интересным свойством, что каждое число представляет собой сумму двух чисел, расположенных непосредственно над ним.

В этом посте мы будем использовать треугольник Паскаля, чтобы продемонстрировать, как рекурсия (то есть процедура, которая вызывает сама себя в своем определении) может использоваться для облегчения решения сложных проблем, используя примеры, написанные как на Haskell, так и на JavaScript.

Треугольник Паскаля построен так, что первая строка имеет одно число: 1. Каждая дополнительная строка добавляет одно дополнительное число. Таким образом, в третьей строке три числа; 1542-я строка содержит 1542 номера. Каждое число представляет собой сумму двух чисел над ним, за исключением цифры 1 на вершине.

Если мы хотим решить проблему рекурсивно, мы начинаем с того, что легко. Что очевидного в треугольнике Паскаля? Итак, для начала мы просто постулировали, что число в строке 1 равно 1. (Это единственное число в треугольнике, которое не является суммой чисел над ним.) Мы также видим этот первый и последний столбцы в каждом из них. строка будет равна 1. Причина в том, что каждая из них является суммой 1 и ничего (т. е. 0).

Допустим, нам нужна функция - назовем ее pt, которая принимает два целых числа: одно представляет строку, а второе - столбец. pt должен вернуть число в этой позиции. Например, pt 1 1 должен возвращать 1, а pt 3 2 должен возвращать 3. (Обратите внимание, что мы не используем нумерацию с нуля для наших строк и столбцов).

Наша подпись типа будет pt :: (Integer a) => a -> a -> a. То есть is pt функция, которая принимает два целых числа и возвращает целое число.

Начните с простых ответов

Придумывая рекурсивное решение, мы начинаем с простых ответов. Какой здесь самый простой случай? Ну, число в строке 1 столбца 1 равно 1!

-- Haskell
pt :: Integer -> Integer -> Integer
pt 1 1 = 1
// JavaScript
function pt(row, col) {
  if (a === 1 || b === 1) {
    return 1;
  }
}

Это было просто. Что еще можно сказать наверняка? Во-первых, в столбце меньше 1. Ничего = ноль. Поэтому, если мы запрашиваем у pt позицию, в которой столбец меньше 1, pt должен вернуть 0.

-- Haskell
pt :: Integer -> Integer -> Integer
pt row col
  | row == 1 && col == 1 = 1
  | col < 1 = 0
// JavaScript
function pt(row, col) {
  if (row === 1 && col === 1) {
    return 1;
  } else if (col < 1) {
    return 0;
}

Подумайте об этом, если позиция столбца меньше 1, это просто особый случай, когда число находится за пределами треугольника Паскаля (в данном случае слева). Что делать, если положение столбца находится вне треугольника с правой стороны? Тоже было бы ноль. Мы знаем, что общее количество столбцов в строке равно номеру строки. Таким образом:

-- Haskell
pt :: Integer -> Integer -> Integer
pt row col
  | row == 1 && col == 1 = 1
  | col < 1 || col > row = 0
// JavaScript
function pt(row, col) {
  if (row === 1 && col === 1) {
    return 1;
  } else if (col < 1 || col > row) {
    return 0;
  }
}

Что тогда после простых вопросов?

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

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

-- Haskell
pt :: Integer -> Integer -> Integer
pt row col
  | row == 1 && col == 1 = 1
  | col < 1 || col > row = 0
  | otherwise = (pt (row - 1) (col - 1)) +
                (pt (row - 1) (col))
// JavaScript
function pt(row, col) {
  if (row === 1 && col === 1) {
    return 1;
  } else if (col < 1 || col > row) {
    return 0;
  } else {
    return (pt (row - 1, col - 1)) +
           (pt (row - 1, col));
  }
}

Магия!

И вот оно! pt 1 1 возвращает 1, pt 3 2 возвращает два, а pt 17 5 возвращает 1820.

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

Также следует иметь в виду, что такого рода рекурсивный вызов является формой рекурсии дерева. Чем больше число, тем больше ресурсов потребует процедура. Скорость роста здесь экспоненциальная. Мой компьютер быстро дал мне ответ на pt 17 5; Я все еще жду ответа на pt 71 5.