Create a list of results of all recursive calls performed by a function call

Question

I want to achieve the same result I can get with this code:

function fibs(n) {
  let fibs = []
  for (let i = 0; i <= n; i++) {
    if ((i <= 1)) fibs.push(i)
    else fibs.push(fibs[i - 1] + fibs[i - 2])
  }
  return fibs
}

console.log( fibs(8) )

with a recursive function.

Obviously, when you console.log(fibs(8) it renders a list like this: [0, 1, 1, 2, 3, 5, 8, 13, 21]

My recursive function looks like this:

function fibsRec(n) {
  if (n < 2) return n
  return fibsRec(n - 1) + fibsRec(n - 2)
}

console.log( fibsRec(8) )

and if you console.log(fibsRec(8)) it returns 21, which is the 8th Fibonacci number, but doesn't give me the list of all the Fibonacci numbers before it. How can I get the list without a loop, just from my recursive function?

How can I get the same outcome as fibs() with fibsRec()

Answer 1

where it goes wrong

Let's review. If fibsRec is meant to return an array, we can first notice that return n isn't going to work. n is just a number and we need an array.

function fibsRec(n) {
  if (n < 2) return n                    // <- problem one
  return fibsRec(n - 1) + fibsRec(n - 2) // <- problem two
}

Second, if fibsRec is going to be returning arrays, we cannot simply call + for fibsRec(n - 1) and fibsRec(n - 2). Watch what happens if we were to try -

const a = [1,2,3]
const b = [4,5,6]
console.log(a + b) // 1,2,34,5,6

Maybe you're thinking that's an odd result. Really JavaScript should throw an error for such misuse of +, but instead it tries its "best" to perform the addition. To do so, it coerces each array to a string first, then combines the strings together -

const a = [1,2,3]
const b = [4,5,6]
console.log(String(a)) // 1,2,3
console.log(String(b)) // 4,5,6
console.log(a + b) // 1,2,34,5,6

behaviour-oriented design

To understand how fibsRec needs to behave, let's first define some outputs for known inputs -

f(n)	output
f(0)	[]
f(1)	[0]
f(2)	[0,1]
f(3)	[0,1,1]
f(4)	[0,1,1,2]
f(5)	[0,1,1,2,3]
f(6)	[0,1,1,2,3,5]
...	...

To fix the first problem, easy mode, change return n to return a range 0..n instead -

function fibsRec(n) {
  if (n < 2) return range(0,n)           // <- fix one
  return fibsRec(n - 1) + fibsRec(n - 2) // ...
}

const range = (a, b) =>
  a >= b
    ? []
    : [a, ...range(a + 1, b)]

you can't + arrays, but you can fibplus them...

To fix the second problem, we need a function that can "add" fibonacci sequences (arrays) because + just isn't going to cut it. We'll call our function fibplus -

function fibsRec(n) {
  if (n < 2) return range(0,n)
  return fibplus(fibsRec(n - 1), fibsRec(n - 2)) // <- fix two
}

We just have to define how fibplus will add the sequences to achieve the correct result. Let's work off an example. To compute fib(6) we need to "add" fib(5) and fib(4). We could just try stacking the two sequences and adding down to get the result -

         0 1 1 2 3   == fib(4)
     + 0 1 1 2 3 5   == fib(5)
------------------------------------
       0 1 2 3 5 8   ~~ fib(6)

It's very close to fib(6) but notice it's off by one. Watch what happens when we prepend a 1 to the smaller number before adding -

1 ->   1 0 1 1 2 3
     + 0 1 1 2 3 5
------------------------------------
       1 1 2 3 5 8   ~~ fib(6)   

Now if we prepend a 0 to the sum ...

       1 0 1 1 2 3
     + 0 1 1 2 3 5
------------------------------------
0 -> 0 1 1 2 3 5 8   == fib(6)   

We now have fib(6)! We just need to write fibplus to implement this adding technique -

const fibplus = (a, b) =>
  [0, ...zip(add, a, [1, ...b])]
  
const zip = (f, a, b) =>
  a.map((v, i) => f(v, b[i]))
  
const add = (a, b) => a + b

functioning demo

Run the snippet below to verify the result in your own browser -

const fib = n =>
  n < 2
    ? range(0, n)
    : fibplus(fib(n - 1), fib(n - 2))
    
const range = (a, b) =>
  a >= b
    ? []
    : [a, ...range(a + 1, b)]
    
const fibplus = (a, b) =>
  [0, ...zip(add, a, [1, ...b])]
  
const zip = (f, a, b) =>
  a.map((v, i) => f(v, b[i]))
  
const add = (a, b) => a + b

console.log(String(fib(20)))

0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181

visualizing

So indeed we were able to make fibsRec work using fibplus, but by mirroring the original recursive process we inherited a lot of inefficiency as well. We can see the sheer amount of duplicated work -

@WillNess comments below and explains another way fibplus can be rewritten to save some work, but the real drawback of the approach above is the resulting exponential process. Let's see some other ways to get the result we are looking for.

other processes

I like the way you asked the question: "How can I get the same outcome?". Different procedures evolve different processes, and we are not required to create a recursive branching process. Instead a linear iterative process is more efficient and better suited for the desired output.

Note fibs returns an array, but I cast the output as a string for more digestible output -

const fibs = (n, a = 0, b = 1) =>
  n <= 0
    ? []
    : [a, ...fibs(n - 1, b, a + b)]
    
console.log(String(fibs(10)))

So how does it work? Recursion is a functional heritage and so using it with functional style yields the best results. This means avoiding things like mutation, variable reassignments, or other side effects. When a function is referentially transparent, its call can be replaced by its return value, without changing the meaning of our program.

fibs(6)
== fibs(6, 0, 1)
== [0, ...fibs(5, 1, 1)]
== [0, ...[1, ...fibs(4, 1, 2)]]
== [0, ...[1, ...[1, ...fibs(3, 2, 3)]]]
== [0, ...[1, ...[1, ...[2, ...fibs(2, 3, 5)]]]]
== [0, ...[1, ...[1, ...[2, ...[3, ...fibs(1, 5, 8)]]]]]
== [0, ...[1, ...[1, ...[2, ...[3, ...[5, ...fibs(0, 8, 13)]]]]]]
== [0, ...[1, ...[1, ...[2, ...[3, ...[5, ...[]]]]]]]
== [0, ...[1, ...[1, ...[2, ...[3, ...[5]]]]]]
== [0, ...[1, ...[1, ...[2, ...[3, 5]]]]]
== [0, ...[1, ...[1, ...[2, 3, 5]]]]
== [0, ...[1, ...[1, 2, 3, 5]]]
== [0, ...[1, 1, 2, 3, 5]]
== [0, 1, 1, 2, 3, 5]

wasteful intermediate arrays

You might notice that the many intermediate arrays is somewhat wasteful and the result could be accomplished with a single array. Let's make a push helper to do just that -

const push = (arr, val) =>
  (arr.push(val), arr) 

const fibs = (n, a = 0, b = 1, r = []) =>
  n == 0
    ? r
    : fibs(n - 1, b, a + b, push(r, a))

console.log(String(fibs(10)))

Let's see how this one works -

fibs(6)
== fibs(6, 0, 1, [])
== fibs(5, 1, 1, [0])
== fibs(4, 1, 2, [0,1])
== fibs(3, 2, 3, [0,1,1])
== fibs(2, 3, 5, [0,1,1,2])
== fibs(1, 5, 8, [0,1,1,2,3])
== fibs(0, 8, 11, [0,1,1,2,3,5])
== [0,1,1,2,3,5]

streams

Another fun way to calculate sequences of fibonacci numbers is to use streams. Streams deliver data over time as it is needed, instead of all at once. Because streams allow us to consume only as much as need, we can actually define fibs as an infinite stream. Notice it is no longer a function -

const fibs =
  stream(0, _ =>
    stream(1, _ =>
      streamAdd(fibs, fibs.next)))

The building blocks of our streams are emptyStream and stream. To construct a non-empty stream, we give provide any value to stream and a thunk _ => ... where ... is computation of the next value, if any -

const emptyStream =
  Symbol('emptyStream')

const stream = (value, next) => ({
  value,
  get next() { delete this.next; return this.next = next() }
})

Streams as defined here are not the same as JavaScript's built-in generators. The primary difference is they are persistent, meaning they can be replayed any number of times. JavaScript's generators have an internal "cursor" and once it advances, you can never rewind it. This is important for our fibs stream because you can see it consumes itself twice. If we used generators, advancing the generator for one operation would permanently advance it for all others.

Next we define generic stream operations. streamAdd combines two streams of numbers using addition -

const streamAdd = (s1, s2) =>
  s1 === emptyStream || s2 === emptyStream
    ? emptyStream
    : stream(s1.value + s2.value, _ => streamAdd(s1.next, s2.next))

And because fibs is infinite, we need some way to limit how much we bite off. streamTake will terminate an infinite stream after that limit is reached -

const streamTake = (s = emptyStream, n = 0) =>
  s === emptyStream || n <= 0
    ? emptyStream
    : stream(s.value, _ => streamTake(s.next, n - 1))

Finally, to fulfill the desired output, we convert the finite stream to an array -

function streamToArray(s = emptyStream) {
  const r = []
  while (s != emptyStream) {
    r.push(s.value)
    s = s.next
  }
  return r
}

Run the stream demo below to verify the result in your browser -

const emptyStream =
  Symbol('emptyStream')

const stream = (value, next) => ({
  value,
  get next() { delete this.next; return this.next = next() }
})
  
const streamAdd = (s1, s2) =>
  s1 === emptyStream || s2 === emptyStream
    ? emptyStream
    : stream(s1.value + s2.value, _ => streamAdd(s1.next, s2.next))

const streamTake = (s = emptyStream, n = 0) =>
  s === emptyStream || n <= 0
    ? emptyStream
    : stream(s.value, _ => streamTake(s.next, n - 1))

function streamToArray(s = emptyStream) {
  const r = []
  while (s != emptyStream) {
    r.push(s.value)
    s = s.next
  }
  return r
}

const fibs =
  stream(0, _ =>
    stream(1, _ =>
      streamAdd(fibs, fibs.next)))

console.log(String(streamToArray(streamTake(fibs, 20))))

0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181