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()
CodePudding user response：
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,6Maybe 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,6behaviour-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
CodePudding user response：
I would do this like this (it's also a little bit faster because of caching):
function fibsRec(n) {
const cache = {
1: 1,
0: 1
}
rec(n)
return Object.values(cache)
function rec(n) {
if (cache[n]) return cache[n]
cache[n - 1] ??= rec(n - 1)
cache[n - 2] ??= rec(n - 2)
return cache[n - 1] cache[n - 2]
}
}
console.log(fibsRec(8))CodePudding user response：
Of course the easy answer would be to make a wrapper function that loops and calls fibsRec(i) each time, but that's not what you're looking for.
First, you need to think about what fibsRec is doing to see why this isn't naturally as simple as it sounds. As you already know it gets the nth fibonacci number by finding the (n-1)th and (n-2)th and to get those, it keeps going further back.
But that means that to get the n-1 and n-2 numbers, you need to generate the sequence to n-1 and n-2, not only that, but when you start generating that sequence for, let's say n-1, and you have to calculate it's previous indices, then you need two more sequences, and so on and so on. It's extremely inefficient.
But the reason I'm bringing this up, is to say that we can't just create an empty array and have it push the number we'd return before returning it, because we're making so many sequences, our array is gonna contain all those results.
Look at this:
function fibArray(n) {
const output = [];
function fibsRec(n) {
if (n < 2) {
output.push(n)
return n;
}
let num = fibsRec(n - 2) fibsRec(n - 1)
output.push(num);
return num;
}
fibsRec(n);
return output
}
console.log( fibArray(8) )See how many times we're calculating a number on the fibonacci sequence?
We definitely can't directly use this approach. But what we can use is dynamic programming. What we'll do is, memoize (save) each fibonacci number we calculate to a dictionary, and the next time we're looking for it, instead of recursing a new sequence, we'll just get it from the dictionary directly.
That way, we're getting each fibonacci number only once. So when we calculate it, we can push it to our output array, and it'll be a clean fibonacci sequence.
function fibArray(n) {
const output = [];
const fibs = {}; // Create memo (a dictionary)
function fibsRec(n) {
if (fibs[n]) return fibs[n]; // Check memo
if (n < 2) {
fibs[n] = n;
output.push(n)
return n;
}
let num = fibsRec(n - 2) fibsRec(n - 1) // Start with n-2 to eventually call fibsRec(0) before fibsRec(1) and push them in that order
fibs[n] = num; // Memoize
output.push(num);
return num;
}
fibsRec(n);
return output
}
console.log( fibArray(8) )