标量单位类型，斐波那契回溯深度函数 [英] Scala unit type, Fibonacci recusive depth function

问题描述

所以我想在scala中编写一个Fibonacci函数，该函数输出如下所示的树:

So I want to write a Fibonacci function in scala that outputs a tree like so:

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的斐波那契数字的末尾，我无法在我的depthFibonacci函数中实现此功能，否则该类型将成为Unit.我该如何解决?

As you can see there is no "= " at the end of any fibonacci numbers greater than 1, and I am unable to implement this in my depthFibonacci function or else the type becomes Unit. How can I fix this?

推荐答案

这与您追求的目标接近吗?

Is this close to what you're after?

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 ，即使没有适当的尾调用递归，我们也可以实现尾调用消除.

---

Stack Safe

As it turns out, we can achieve tail call elimination, even without proper tail call recursion, by using TailCalls from the standard library.

我们从 ScalaDocs页面，并添加3条策略性放置的 println()语句.

We start with the Fibonacci implementation as found on the ScalaDocs page and add 3 strategically placed println() statements.

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

但是事情并不像看起来那样.

But things aren't quite what they seem.

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

这就是依靠副作用来获得结果的危险.

Thus are the dangers of relying on side effects for your results.

这篇关于标量单位类型，斐波那契回溯深度函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！