Как написать рекурсивную функцию, которая выводит ряд Фибоначчи

180

13 июля 2022, 03:40

Необходимо написать рекурсивную функцию, которая будет выводить ряд Фибоначчи в консоль. Не понимаю, как это сделать

function fib(n) {
    if(n <= 1){
        console.log(n)
    } else {
        for(let i=0;i<n;i++){
            console.log(fib(i - 1) + fib(i - 2))
        }
    }
    return n <= 1 ? n : fib(n - 1) + fib(n - 2);
  }
fib(5);

Answer 1

Вот так, например.

function print_fib(n) {
  if (n == 0) {
    console.log(0);
    return [1, 0]; // Всем известно, что fib(-1) = 1 =)
  }
  const [n_2, n_1] = print_fib(n-1);
  console.log(n_1 + n_2);
  return [n_1, n_1 + n_2];
}
print_fib(15)

А с такой экспоненциальной рекурсией, как у вас, реализовать линейный вывод довольно затруднительно(слишком много лишних вызовов функции):

function fib(n, trace = false, depth = 0) {
  if (n >= 2 && trace) console.log('  '.repeat(depth), `fib(${n}) вызывает fib(${n-1}) и fib(${n-2})`);
  const res = n < 2 ? n : fib(n - 1, trace, depth + 1) + fib(n - 2, trace, depth + 1);
  if (trace)
    console.log('  '.repeat(depth), `fib(${n}) выводит ${res}`);
  else
    console.log(res);
  return res;
}
function print_fib(n, service_call=false) {
  const res = n < 2 ? n : print_fib(n - 1, service_call) + print_fib(n - 2, true);
  if (!service_call) console.log(res);
  return res;
}

<button onclick="console.clear(); fib(5, false);">fib(5) Без трассировки</button>
<button onclick="console.clear(); fib(5, true);">fib(5) С трассировкой</button>
<button onclick="console.clear(); print_fib(5);">fib(5) рабочая версия</button>

Answer 2

А можно генератором

function *fibonacci(n, current = 0, next = 1) {
  if (n === 0) {
    return current;
  }
  yield current;
  yield *fibonacci(n-1, next, current + next);
}
console.log([...fibonacci(40)])

Либо вообще бесконечным генератором:

function* fibonacci(a=0n,b=1n){for(;a=b+(b=a);)yield a}

ПОСЛЕДНИЕ ВОПРОСЫ

Все вопросы

ТОП-10

Все популярные вопросы

js Array.prototype.reduce() что значит =>?

Нужно из двумерного массива [1, 2, [3, 4]] сделать одномерный var arr1 = [1, 2,3, 4];

174

javascript

Сортировка классов html

Есть 2 кнопки (чекбоксы) и 3 картинкиКак написать код так, чтобы при нажатии на 1 кнопку вылезала 1 картинка, при нажатии на 2 кнопку вылазила...

233

javascript

Как передать несколько параметров в AJAX функцию?

пытаюсь передать два параметра функции, но при нажатии на кнопку выпадает ошибка

215

javascript

Отключить возможность ввода букв

Есть спан с возможностью редактирования, использовать просто инпут не вариант потому что он сразу ломает всю версткуНужно чтобы при нажатии...

215