Scala 单位类型，斐波那契递归深度函数

Question

所以我想在 scala 中编写一个斐波那契函数，输出如下所示的树:

fib(3)
| fib(2)
| | fib(1)
| | = 1
| | fib(0)
| | = 0
| = 1
| fib(1)
| = 1
= 2

我当前的代码如下:

 var depth: Int = 0
  def depthFibonacci(n:Int, depth: Int): Int={
    def fibonnaciTailRec(t: Int,i: Int, j: Int): Int = {
      println(("| " * depth) + "fib(" + t + ")")
      if (t==0) {
        println(("| " * depth) + "=" + j)
        return j
      }
      else if (t==1) {
        println (("| " * depth) + "=" + i)
        return i
      }
      else {
        depthFibonacci(t-1,depth+1) + depthFibonacci(t-2,depth+1)
      }
    }
    fibonnaciTailRec(n,1,0)
  }
  println(depthFibonacci(3,depth))

运行时，看起来像:

fib(3)
| fib(2)
| | fib(1)
| | =1
| | fib(0)
| | =0
| fib(1)
| =1
2

正如您所看到的，任何大于 1 的斐波那契数末尾都没有“=”，并且我无法在深度斐波那契函数中实现此功能，否则类型将变为 Unit。我该如何解决这个问题？

Answer 1

这接近你想要的吗？

def depthFib(n:Int, prefix:String = ""):Int = {
  println(s"${prefix}fib($n)")
  val res = n match {
    case x if x < 1 => 0
    case 1 => 1
    case _ => depthFib(n-1, prefix+"| ") +
              depthFib(n-2, prefix+"| ")
  }
  println(s"$prefix= $res")
  res
}

用法:

depthFib(3)

---

堆栈安全

事实证明，即使没有适当的尾调用递归，我们也可以通过使用标准库中的 TailCalls 来实现尾调用消除。

我们从 ScalaDocs page 上找到的斐波那契实现开始并添加 3 个策略性放置的 println() 语句。

import scala.util.control.TailCalls._

def fib(n: Int, deep:Int=0): TailRec[Int] = {
  println(s"${"| "*deep}fib($n)")
  if (n < 2) {
    println(s"${"| "*deep}= $n")
    done(n)
  } else for {
    x <- tailcall(fib(n-1, deep+1))
    y <- tailcall(fib(n-2, deep+1))
  } yield {
    println(s"${"| "*deep}= ${x+y}")
    x + y
  }
}

用法:

fib(3).result

但事情并不完全像看上去的那样。

val f3 = fib(3)  // fib(3)
println("Wha?")  // Wha?
f3.result        // | fib(2)
                 // | | fib(1)
                 // | | = 1
                 // | | fib(0)
                 // | | = 0
                 // | = 1
                 // | fib(1)
                 // | = 1
                 // = 2

这就是依赖副作用来获得结果的危险。