c++ - recursividad - serie de fibonacci algoritmo

Fibonacci recursivo

Question

Me está costando entender por qué

#include <iostream>

using namespace std;

int fib(int x) {
    if (x == 1) {
        return 1;
    } else {
        return fib(x-1)+fib(x-2);
    }
}

int main() {
    cout << fib(5) << endl;
}

da como resultado una falla de segmentación. Una vez que x llega a 1, ¿no debería eventualmente regresar?

Answer 1

¿Por qué no usar el algoritmo iterativo?

int fib(int n)
{
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }           
    return b;
}

Answer 2

Creo que es la mejor solución de fibonacci que usa recursividad.

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
ull FIBO[100005];
using namespace std;
ull fibo(ull n)
{
    if(n==1||n==0)
        return n;
    if(FIBO[n]!=0)
        return FIBO[n];
    FIBO[n] = (fibo(n-1)+fibo(n-2));
    return FIBO[n];
}
int main()
{
    for(long long  i =34;i<=60;i++)
        cout<<fibo(i)<<" " ;
    return 0;
}

Answer 3

Creo que esta solución es corta y parece bonita:

long long fib(int n){
  return n<=2?1:fib(n-1)+fib(n-2);
}

Editar: como mencionó jweyrich, la verdadera función recursiva debería ser:

long long fib(int n){
      return n<2?n:fib(n-1)+fib(n-2);
    }

(porque fib (0) = 0. pero base en la fórmula recursiva anterior, fib (0) será 1)

Para entender el algoritmo de recursión, debe dibujar en su papel, y lo más importante es: "Piense normal como a menudo".

Answer 4

Cuando x==2 llamas fib(1) y fib(0) :

return fib(2-1)+fib(2-2);

Considere lo que sucederá cuando se evalúe fib(0) ...

Answer 5

La razón es porque la secuencia de Fibonacci comienza con dos entidades conocidas, 0 y 1. Su código solo verifica uno de ellos (siendo uno).

Cambia tu código a

int fib(int x) {
    if (x == 0)
        return 0;

    if (x == 1)
        return 1;

    return fib(x-1)+fib(x-2);
}

Para incluir tanto 0 como 1.

Answer 6

Mi solución es:

#include <iostream>


    int fib(int number);

    void call_fib(void);

    int main()
    {
    call_fib();
    return 0;
    }

    void call_fib(void)
    {
      int input;
      std::cout<<"enter a number/t";
      std::cin>> input;
      if (input <0)
      {
        input=0;
        std::cout<<"that is not a valid input/n"   ;
        call_fib();
     }
     else 
     {
         std::cout<<"the "<<input <<"th fibonacci number is "<<fib(input);
     }

    }





    int fib(int x)
    {
     if (x==0){return 0;}
     else if (x==2 || x==1)
    {
         return 1;   
    }

    else if (x>0)
   {
        return fib(x-1)+fib(x-2);
    }
    else 
     return -1;
    }

devuelve fib (0) = 0 y error si es negitive

Answer 7

Por definición, los primeros dos números en la secuencia de Fibonacci son 1 y 1, o 0 y 1. Por lo tanto, debe manejarlo.

#include <iostream>
using namespace std;

int Fibonacci(int);

int main(void) {
    int number;

    cout << "Please enter a positive integer: ";
    cin >> number;
    if (number < 0)
        cout << "That is not a positive integer./n";
    else
        cout << number << " Fibonacci is: " << Fibonacci(number) << endl;
}

int Fibonacci(int x) 
{
    if (x < 2){
     return x;
    }     
    return (Fibonacci (x - 1) + Fibonacci (x - 2));
}

Answer 8

Esta es mi solución al problema de fibonacci con recursión.

#include <iostream>
using namespace std;

int fibonacci(int n){
    if(n<=0)
        return 0;
    else if(n==1 || n==2)
        return 1;
    else
        return (fibonacci(n-1)+fibonacci(n-2));
}

int main() {
    cout << fibonacci(8);
    return 0;
}

Answer 9

if(n==1 || n==0){
    return n;
}else{     
    return fib(n-1) + fib(n-2);
}

Sin embargo, usar recursión para obtener el número de fibonacci es una mala práctica, porque la función se llama aproximadamente 8,5 veces más que el número recibido. Por ejemplo, para obtener el número de fibonacci de 30 (1346269) - ¡la función se llama 7049122 veces!

Answer 10

int fib(int n) {
    if (n == 1 || n == 2) {
        return 1;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

en la secuencia de Fibonacci, los primeros 2 números siempre se siguen hasta 1, entonces cada vez que el valor se vuelve 1 o 2, debe regresar 1

Answer 11

int fib(int x) 
{
    if (x < 2)
      return x;
    else 
      return (fib(x - 1) + fib(x - 2));
}

Answer 12

int fib(int x) 
{
    if (x == 0)
      return 0;
    else if (x == 1 || x == 2) 
      return 1;
    else 
      return (fib(x - 1) + fib(x - 2));
}