# Tribonacci numbers using tail-recursion

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?

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

1 Like

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

`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

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

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

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

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

@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

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.

@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.

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

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

@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

This blog post might be a useful introduction. Note that â€śdistinctâ€ť doesnâ€™t necessarily mean â€śdisjunctâ€ť - the trampoline example uses both.

3 Likes