评估递归函数，我给这个函数，并要求手动评估g 5。我发现答案是25，但这是不正确的。正确答案是63.有人能帮我理解为什么吗？感谢在Haskell
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
你只需要一步的想出来步：
(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
你的问题是，你正在使用的原始值0，而不是在递归的终点返回什么(g n)。
在你的计算中，你会混淆术语的嵌套。它们应该嵌套而不是分开总结。
评估此类函数的方法是将函数应用程序替换为函数体，其参数由给定参数替换。我会做的前几个步骤，然后你可以接管：
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的回答当然是容易计算，但这种技术更普遍，更内嵌代码是如何实际工作。
虽然这不是你的问题，它很容易被归纳证明
g n = 2^(n+1)-1
所以
g 5 = 2^6 - 1 --> 63
你的括号是错误的。没有做任何的减少（比扩大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
有多少次你尝试对其进行评估？可能你只是搞砸了一些计算。也许写下为什么你认为它应该是42，所以我们可以指出你的错误。 – jpath