Tribonacci numbers using tail-recursion

Question
1

There is this well-known way to generate the Fibonacci numbers

val fibs:LazyList[Int] = 0 #:: 1 #:: (fibs zip fibs.tail).map{ t => t._1 + t._2 }

I tried to generalize this approach for computing tribonacci numbers in the following way

val tribs: LazyList[Int] = 0 #:: 0 #:: 1 #:: (tribs zip tribs.tail zip tribs.tail.tail ).map (t => t._1 + (t._2)._1 + (t._2)._2)

however I get

 error: value _1 is not a member of Int
 error: value _2 is not a member of Int

How this can be repaired? How this can be generalized to n-nacci sequences preserving functional style and tail-recursion?

2

I think in this case it would be simpler to use unfold

1 Like
3

in the case of tribonacci I managed to correct the code

val tribs: LazyList[Int] = 0 #:: 0 #:: 1 #:: (tribs zip tribs.tail.zip(tribs.tail.tail) ).map (t => t._1 + t._2._1 + t._2._2)

With unflod you probably mean something like this

 val fibonacci: Iterator[Int] = 
  Iterator.unfold((0, 1)) {
  case (x, y) => Some((x, (y, x + y)))
}

but how would you generalize to arbitrary n-nacci numbers? Also, is the code of unfold tail-recursive?

2 Likes
4

LazyList has #unfold(), too. You could generalize the tuple to some collection. Naive take:

def nbonaccis(n: Int): LazyList[Int] = {
  val init = List.fill(n - 1)(0) :+ 1
  LazyList.from(init) ++ LazyList.unfold(init){ ps => /* ... */ }
}
4 Likes
5

Yes, thank you! But how can I see that this method is tail recursive?

6

You can’t. #unfold() is not tail-recursive, it’s lazy. Your #fibs (and #tribs) variant isn’t tail-recursive either - the recursive call to #fibs() is not the outermost/final one (and there’s multiple calls to it, anyway). Tail recursion and laziness are distinct strategies for stack safety.

4 Likes
7

Hello @yarchik, FWIW, here is a really minor suggestion, in case you like it, replacing that with

{ case (n1, n2) => n1 + n2 }
1 Like
8

@sangamon @BalmungSan @yarchik nice - fibUnfold goes right next to fibFold and fibIter in my collection

def fibFold(n: Int): Long =
  (1 to n).foldLeft((0L,1L)) { 
    case ((n1, n2), _) => (n2, n1 + n2)
  }(0)

def fibIter(n: Int): Long =
  LazyList.iterate((0L,1L)) {
    case (n1, n2) => (n2, n1 + n2)
  }(n)(0)

def fibUnfold(n: Int): Long =
  LazyList.unfold((0L,1L)) {
    case (n1, n2) => Some((n1, (n2, n1 + n2)))
  }(n)
2 Likes
9

Just to expand on @sangamon answer, n-nacci numbers can be generated using lazy list approach

 def nbonacci(n: Int): LazyList[Int] = {
        val init = List.fill(n - 1)(0) :+ 1
        LazyList.unfold(init){ 
         case(x) => Some( (x.head, x.tail :+ x.sum) )
        }
      }

It should be noted that LazyList.from(init) ++ is not needed.

10

@sangamon I am very puzzled by your statement “Tail recursion and laziness are distinct strategies for stack safety.” Can you please expand or simply point me in right direction.

11

@yarchik assuming for a moment that you are not already thoroughly well versed in the subjects of tail recursion and laziness, here are two decks that you might find useful, the first one mainly, but not only, for tail recursion, and the second one for laziness. Apologies in advance if they are of no use to you (please download for original quality):

12

a small number of errata in the decks (see details in the blurb on slideshare) are addressed in these versions:

13

@yarchik please skip the first 19 slides of the first deck (at least on a first reading) - the key content is Sergei Winitzki’s great explanation of tail recursion.

@yarchik P.S. doh, scrap the above quote and sentence: they key content on tail recursion in the first deck is from slide 13 to 18, and yes, it is Sergei Winitzki’s great explanation of tail recursion.

1 Like
14

This blog post might be a useful introduction. Note that “distinct” doesn’t necessarily mean “disjunct” - the trampoline example uses both.

3 Likes