Scala unit type, Fibonacci recusive depth function

user_14968884 0
Viewed 138

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

and my current code is as follows:

 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))

which, when run, looks like:

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

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?

fibonacci recursion scala
1 Answers

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
}

usage:

depthFib(3)

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.

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
  }
}

usage:

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.

user_49931280
Related