ricorsivo Fibonacci

Question

Sto avendo difficoltà a capire il motivo per cui

#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; 
} 

risultati in un errore di segmentazione. Una volta che x scende a 1 non dovrebbe eventualmente tornare?

Answer 1

Quando x==2 si chiama fib(1) e fib(0):

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

Considerate che avverrà fib(0) viene valutata ...

Answer 2

Il motivo è perché successione di Fibonacci inizia con due entità conosciute, 0 e 1. Il tuo codice controlla solo uno di essi (essendo uno).

modificare il codice per

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

    if (x == 1) 
     return 1; 

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

per includere sia 0 e 1.

Answer 3

Perché non usare 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 4

Penso che questa soluzione è breve e sembra sembra piacevole:

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

Edit: come jweyrich accennato, vera funzione ricorsiva dovrebbe essere:

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

(perché fib (0) = 0. ma base su formula ricorsiva, fib (0) sarà 1)

Per comprendere l'algoritmo di ricorsione, si dovrebbe attingere al tuo giornale e la cosa più importante è: "Pensa normale come spesso".

Answer 5

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

nella sequenza di Fibonacci primi 2 numeri sequel sempre a 1, quindi ogni volta che il valore è diventato 1 o 2 deve restituire 1

Answer 6

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)); 
} 

Answer 7

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

Answer 8

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

Tuttavia, utilizzando la ricorsione per ottenere Fibonacci il numero è una cattiva pratica, perché la funzione è chiamata circa 8,5 volte rispetto al numero ricevuto. E.g. per ottenere il numero di fibonacci di 30 (1346269) - la funzione è chiamata 7049122 volte!

Answer 9

Per definizione, i primi due numeri nella sequenza di Fibonacci sono 1 e 1 oppure 0 e 1. Pertanto, è necessario gestirlo.

#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 10

Questa è la mia soluzione a Fibonacci problema con la ricorsione.

#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 11

La mia soluzione è:

#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; 
    } 

restituisce fib (0) = 0 e di errore se negitive

Answer 12

penso che sia la migliore soluzione di Fibonacci utilizzando la ricorsione.

#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; 
}