Haskell - 计算递归次数

Question

我有一个简单的函数来计算下面的第n个fibonnaci数:

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

但我感兴趣的是计算此函数的递归数量的方法.有什么想法怎么做？

Answer 1

这让人想起所谓的作家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