haskell - Haskell - 计算递归次数

Question

我有一个简单的函数来计算下面的第 n 个斐波那契数：

fibonacci :: Integer -> Integer
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = (fibonacci (n-1) ) + (fibonacci (n-2))

但我对计算此函数的递归次数的方法很感兴趣。任何想法如何做到这一点？

Answer 1

这让人想起所谓的 Writer monadsigfpe的说明。您可能会像这样更系统地执行此操作：

import Control.Monad.Trans.Writer
import Control.Monad.Trans
import Data.Monoid

fibwriter :: Int -> Writer (Sum Int) Integer
fibwriter 0 = return 0
fibwriter 1 = return 1
fibwriter n =  do a <- fibwriter (n-1)
                  b <- fibwriter (n-2)
                  tell (Sum (2::Int))
                  return (a + b)

如此使用：

*Fib> runWriter $ fibwriter  11
(89,Sum {getSum = 286})

这是相同的定义，但具有记录每对额外递归对的“副作用”。IO如果我们想在“天真”定义中看到所有疯狂的重新计算，我们还可以添加一个副作用：

fibprint :: Int -> WriterT (Sum Int) IO Integer
fibprint 0 = return 0
fibprint 1 = return 1
fibprint n = do  a <- fibprint (n-1)
                 record a
                 b <- fibprint (n-2)
                 record b
                 return (a + b)
 where  record x = lift (putStr $  ' ' : show x) >> tell (Sum 1)

对于斐波那契 11，这给了我们这个荒谬的重复显示，因为计算爬向 89：

*Fib> runWriterT $ fibprint 11
 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 1 0 1 1 2 1 0 1 3 1 0
 1 1 2 5 13 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 21 1 0 1 1
 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5
 13 34 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 1 0 1 1 2 1 0 1
 3 1 0 1 1 2 5 13 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 21 55
 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 1 0 1 1 2 1 0 1 3 1 0
 1 1 2 5 13 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 21 1 0 1 1
 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5
 13 34(89,Sum {getSum = 286})

Answer 2

recursions :: Integer -> Integer
recursions 0 = 0
recursions 1 = 0
recursions n = recursions (n-1) + recursions (n-2) + 2

对于基本情况，没有递归，对于其他所有情况，我们有两个直接递归调用以及从这两个调用中调用的那些。

您还可以重复使用fibonacci代码，

recursions n = 2*fibonacci (n+1) - 2