CODEWITHSUNDEEP
scalarecursionfibonacci
user14968884
user14968884

Reputation:

Scala unit type, Fibonacci recusive depth function

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?

Upvotes: 2

Views: 162

Answers (1)

jwvh
jwvh

Reputation: 51271

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.

Upvotes: 3

Related Questions