5

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

int fib(int n)
{
 if(n < 3)
     return 1;
 return fib(n - 2) + fib(n - 1);
}

Вот я как бы отталкиваюсь от этого кода. Уже и cout в разные места пытался подставить и методом тыка изменял разные значения... не получается(( Помогите пожалуйста. Спасибо!!!

5
  • Так а что не получается?... все работает: ideone.com/sJUUN2 Что у вас означает "числа до n"?
    – Harry
    13 сен 2017 в 16:00
  • я передаю n в функцию например n = 5. Мне должно вывести на экран 0 1 1 2 . Только нигде не должно быть доп циклов и переменных ни в мейне ни в самой функции. У и получается функция должна быть void и не возвращать а примерно такой void fib(int n) { if(n < 3) 1; cout << fib(n - 2) + fib(n - 1); } 13 сен 2017 в 16:07
  • Решения с использованем рекурсии крайне не желательно, т.к. сложнасть высокая. Лучше использовать цикл.
    – Unick
    13 сен 2017 в 16:19
  • Та я понимаю циклом я умею. А вот задание состоит в том что бы онли рекурсией без доп переменных и циклов. 13 сен 2017 в 16:21
  • точно, не внимательно прочитал
    – Unick
    13 сен 2017 в 16:26

3 ответа 3

4

Задача легко решается, если использовать дополнительную функцию. Хотя на самом деле можно и без нее (если использовать параметры по умолчанию)

#include <iostream>

void fib1(int a, int b, int limit)
{
    if (limit == 0) { return; }
    std::cout << a << std::endl;
    fib1(b,a+b, limit-1);
}

void fib(int n)
{
    fib1(1,1,n);
}

int main() {
    fib(10);
    return 0;
}

данные решение очень "интуитивно", если почитать книги по лиспу:)

1
  • посмотрел внимательно в числа фибоначчи - 48 число уже больше uint32...
    – KoVadim
    14 сен 2017 в 7:22
4

(Вариант без (дополнительной функции/переменных) / параметров по умолчанию / циклов)

Напишем функцию fib так, что если в неё передаётся положительное число n, то она выводит первые n чисел Фибоначчи и возвращает n-ое число Фибоначчи, а если передаётся отрицательное число n, то возвращает -n-ое число Фибоначчи (без вывода):

int fib(int n) {
    if (n > 0) {
        // выводим числа Фибоначчи от 1 до n-1
        fib(n - 1);
        // выводим n-ое число Фибоначчи
        cout << (n <= 2 ? 1 : fib(-(n - 1)) + fib(-(n - 2))) << endl;
    } else {
        n *= -1;
    }
    return n <= 2 ? 1 : fib(-(n - 1)) + fib(-(n - 2));
}

Ideone

5
  • 2
    очень красиво. :) 13 сен 2017 в 16:40
  • красиво, но только работать будет меееееедленнннно.
    – KoVadim
    13 сен 2017 в 17:07
  • @KoVadim, ну да) мне кажется что ТС скорость не особо важна
    – diralik
    13 сен 2017 в 17:09
  • @KoVadim, так задача-то была именно вот так извратиться про рекурсию :) считать подобное рекурсией с точки зрения производительности изначально неверная идея. Исходно, видимо, это учебная задачка на рекурсию. И минимизацию стека в ней. :) 13 сен 2017 в 17:23
  • Если посмотрите на мое решение в откомпилированном виде, то gcc/clang умеют разворачивать хвостовую рекурсию. И стек минимизируется по самое немогу.
    – KoVadim
    13 сен 2017 в 17:46
2
#include <stdio.h>

int fib(int n, bool print=true)
{
  if(n == 2 || n == 1)
  {
    if(print)
       printf("%d\n",1);
    return 1;
  }
  else if(n < 1)
    return 0;
  else
  {
    int res = fib(n - 2, false) + fib(n - 1, true);
    if(print)
        printf("%d\n", res);
    return res;
  }

}

int main()
{
   int N=20;
   fib(N);
}

Если я правильно понял, что Вам надо вывести все числа Фиббоначи до n БЕЗ циклов.

4
  • и без доп переменных, только рекурсия((( 13 сен 2017 в 16:20
  • А что Вы имеете в виду без доп. переменных? У рекурсивной функции не должно быть никаких аргументов, кроме n? 13 сен 2017 в 16:20
  • да аргумент только один и в теле функции не создавать переменных 13 сен 2017 в 16:22
  • @МаксимТымчак это невозможно. Как минимум временные переменные на стеке будут. 13 сен 2017 в 16:27

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.