def fib(n : Int) : Int = {
if (n==0) 0
else if (n==1) 1
else fib(n-1) + fib(n-2)
}
def fib2(n : Int) : String = {
var i = n
var k = 1
var tree = ""
while (i>=1) {
k=1
while (k<=n-i) {tree+="| "; k+=1}
tree += "fib(" ++ i.toString ++ ")" + '\n'
i-=1
}
i=1
while (i<=n-1) {
k=n-i
while (k>=1) {tree+="| "; k-=1}
tree += " = " ++ fib(i).toString + '\n'
k=n-i
while (k>=1) {tree+="| "; k-=1}
tree += "fib(" ++ (i-1).toString ++ ")" + '\n'
k=n-i
while (k>=1) {tree+="| "; k-=1}
tree += " = " ++ fib(i-1).toString + '\n'
i+=1
}
tree+= "= " ++ fib(n).toString
tree
}