Попытка создать эффективный алгоритм для функции в Haskell
Я ищу эффективное решение за полиномиальное время для следующей проблемы:
Реализуем рекурсивную функцию узла x y для вычисления (x, y) -го числа в числовом треугольнике, определенном как
g(x,y) = 0 if |x| > y
= 1 if (x,y) = (0,0)
= sum of all incoming paths otherwise
Сумма всех входящих путей к узлу определяется как сумма значений всех возможных путей от корневого узла (x, y) = (0, 0) до рассматриваемого узла, где в каждом узле (x, y ) путь может продолжаться по диагонали вниз и влево (x − 1, y + 1), прямо вниз (x, y + 1) или по диагонали вниз и вправо (x + 1, y + 1). Значение пути к узлу определяется как сумма всех узлов вдоль этого пути до рассматриваемого узла, но не включая его.
Первые несколько записей в числовом треугольнике приведены в таблице:
\ x -3 -2 -1 0 1 2 3
\
y \ _________________________
|
0 | 0 0 0 1 0 0 0
|
1 | 0 0 1 1 1 0 0
|
2 | 0 2 4 6 4 2 0
|
3 | 4 16 40 48 40 16 4
Сначала я пытаюсь найти наивное решение, вот что у меня есть:
node x y | y < 0 = error "number cannot be negative"
| (abs x) > y = 0
| (x == 0) && (y == 0) = 1
| otherwise = node (x+1) (y-1) + node x (y-1) + node (x-1) (y-1)
Всякий раз, когда я запускаю это, я получаю:
"* Исключение: переполнение стека "?