Haskell尾递归实现斐波那契数列如何仅返回最终数值而非列表

解决方法 #

你可以选择两种修改思路，第一种是不改动现有 helper 逻辑的快速修改，第二种是优化掉不必要的列表存储的高效实现：

方法1：直接取现有返回列表的最后一位

Haskell 内置的last函数可以直接获取列表的最后一个元素，你只需要修改fibo函数的返回类型和调用逻辑即可：

-- 修改后返回单个数值而非列表
fibo :: Integral x => x -> x
fibo n = last $ fiboHelper [0,1] 0 1 n

-- 原有helper逻辑保持不变即可
fiboHelper :: Integral x => [x]->x->x->x->[x]
fiboHelper l x y 0 = l
fiboHelper l x y n = fiboHelper (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1)

修改后调用fibo 3就会直接返回13，和你预期的结果一致。

方法2：优化掉列表存储，直接返回递推结果

你当前的实现里维护整个斐波那契列表其实是不必要的，因为你只需要最终结果，只保留递推的前两项就可以完成计算，内存效率会高很多：

fibo :: Integral x => x -> x
-- 和你原有计数逻辑对齐，取迭代2n+1次的结果
fibo n = fiboHelper 0 1 (2 * n + 1)
  where
    -- 递推helper，只保留前两项和剩余迭代次数
    fiboHelper a b 0 = a
    fiboHelper a b k = fiboHelper b (a + b) (k - 1)

补充：函数式风格的无穷列表实现

如果你想尝试更符合Haskell函数式特性的写法，可以用无穷斐波那契列表直接取值：

fibo :: Integral x => Int -> x
-- 同样按你的计数逻辑取第2n+1项
fibo n = fibs !! (2 * n + 1)
  where
    -- 无穷斐波那契序列，惰性求值只会计算到你需要的位置
    fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

内容的提问来源于stack exchange，提问作者TrynaLearnCode