How to extract all values from Fibonacci numbers to n?

Question

I need to write a function using recursion without using an array at the same time. Which will return all the values of the Fibonacci digits to n. n > 0;

function fib(number) {
  if (number === 1) {
    return "0,1,1";
  }
  if (number === 2) {
    return "0,1,1,2,";
  } else {
    let fibList = fib(number - 1);
    return (fibList += `${number - 2 + number - 1},`);
  }
}
console.log(fib(45));

My code doesn’t work as I want, I don’t know how to fix it.

n=7 “0, 1, 1, 2, 3, 5 “

n=45 “0, 1, 1, 2, 3, 5, 8, 13, 21, 34”

There are 10000s of examples on the net on how to calculate Fibonacci — epascarello, Sep 12 '19 at 13:55
@epascarello and most of them are about recursive programming, too. — VLAZ, Sep 12 '19 at 13:56
Your problem description isn't clear. It is relatively easy to write a recursive function which returns the first `n` Fibonacci numbers. On the other hand, I don't see any natural way to write a recursive function which returns the Fibonacci numbers which are below the number `n`. For most `n`, the output of `f(n)` would be equal to the output of `f(n-1)`. Those are very different problems. Are you sure that you are understanding the question correctly? — John Coleman, Sep 12 '19 at 14:00
I did not find any examples where they do not use an array.And I want without an array. — , Sep 12 '19 at 14:04
@Uncle literally the first three hits for "fibonacci recursive javascript" gave me recursive solutions that didn't use an array. Well, one had the array solution but also a non-array solution. One of the hits was [for SO itself](https://stackoverflow.com/questions/8845154/how-does-the-fibonacci-recursive-function-work). — VLAZ, Sep 12 '19 at 14:16
This is a typical Computer Science issue.Just write an iterative version first and then turn it into a recursive function ;-) — Adder, Sep 12 '19 at 14:21
@VLAZ That SO question solves a different (albeit related) problem. Look at OP's intended output for `n = 45`, it is a string consisting of the first 10 Fibonacci numbers, not the 45th Fibonacci number. It is a trickier problem. — John Coleman, Sep 12 '19 at 14:24

score 1 · Answer 1 · answered Sep 12 '19 at 14:39

Somewhat interesting problem. It helps to use some mathematical theory. It can be shown that a number, n, is a Fibonacci number if and only if either 5*n**2 + 4 or 5*n**2 - 4 is a perfect square (see this for a proof). Using this characterization, it is easy enough to write a recursive function somewhat directly. Here is a Python example which you should be able to port to JavaScript:

import math

def perfect_square(n):
    return int(math.sqrt(n)) ** 2 == n

def is_fib(n):
    return perfect_square(5*n**2 + 4) or perfect_square(5*n**2-4)

def fibs_below(n):
    if n == 1:
        return "0 1 1"
    elif is_fib(n):
        return fibs_below(n-1) + ' ' + str(n)
    else:
        return fibs_below(n-1)

For example:

>>> fibs_below(45)
'0 1 1 2 3 5 8 13 21 34'

How to extract all values from Fibonacci numbers to n?

1 Answers1