Оценка рекурсивной функции в Haskell

Question

Мне дана эта функция и попросили вручную оценить g 5. Я нашел ответ 25, но это неверно. Правильный ответ: 63. Кто-нибудь поможет мне понять, почему? Благодаря

g :: Int -> Int 
g n 
    | n==0  = 1 
    | otherwise = 2 * g (n-1) + 1 

Мой ответ: (2 * 4 + 1) + (2 * 3 + 1) + (2 * 2 + 1) + (2 * 1 + 1) + 1 = 25

Answer 1

Вам просто нужно думать, это шаг за шагом:

(g 5) = 2 * (g 4) + 1 
(g 4) = 2 * (g 3) + 1 
(g 3) = 2 * (g 2) + 1 
(g 2) = 2 * (g 1) + 1 
(g 1) = 2 * (g 0) + 1 
(g 0) = 1 

Затем вилка в значениях от снизу вверх:

2 * 1 + 1 = 3 
2 * 3 + 1 = 7 
2 * 7 + 1 = 15 
2 * 15 + 1 = 31 
2 * 31 + 1 = 63 

Ваша проблема заключается в том, что вы использовали необработанный значение n, а не то, что (g n) вернулись в конце рекурсии.

Answer 2

В ваших расчетах вы перепутались с гнездом терминов. Они должны быть вложенными и не суммироваться отдельно.

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

g 5 
if 5 == 0 then 1 else 2 * g (5-1) + 1 
2 * g (5-1) + 1 
2 * (if (5 - 1) == 0 then 1 else 2 * g ((5-1) - 1) + 1) + 1 
2 * (if 4 == 0 then 1 else 2 * g (4-1) + 1) + 1 
2 * (2 * g (4-1) + 1) + 1 
... 
63 

@ ответ Carcigenicate является, конечно, легче вычислить, но этот метод является более универсальным и более рядным с тем, как на самом деле работает код.

Answer 3

Хотя это не ваш вопрос, это довольно легко показать по индукции, что

g n = 2^(n+1)-1 

Так

g 5 = 2^6 - 1 --> 63 

Answer 4

Ваш скобок неправильно. Не делая никаких сокращений (кроме расширения g), получаем

g 5 
= 2 * g 4 + 1 
= 2 * (2 * g 3 + 1) + 1 
= 2 * (2 * (2 * g 2 + 1) + 1) + 1 
= 2 * (2 * (2 * (2 * g 1 + 1) + 1) + 1) + 1 
= 2 * (2 * (2 * (2 * (2 * g 0 + 1) + 1) + 1) + 1) + 1 
= 2 * (2 * (2 * (2 * (2 * 1 + 1) + 1) + 1) + 1) + 1