Rapide de Fibonacci de la récursivité

Je suis en train d'essayer de se souvenir d'un algorithme de Fibonacci de la récursivité. Suivantes:

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

est pas ce que je cherche parce que c'est gourmand. Cela va croître de façon exponentielle (il suffit de regarder Java récursif de la suite de Fibonacci - le plus gros de l'argument initial les plus inutiles, les appels seront effectués).

Il y a probablement quelque chose comme un "cyclique argument shift", où l'appel précédent de Fibonacci de la valeur de récupérer la valeur au lieu de calculer à nouveau.

InformationsquelleAutor ducin | 2012-12-11

40

peut-être comme ceci:
```
int fib(int term, int val = 1, int prev = 0)
{
 if(term == 0) return prev;
 return fib(term - 1, val+prev, val);
}
```
cette fonction est la queue récursive. cela signifie qu'il pourrait être optimisée et exécuté de façon très efficace. En fait, il obtient optimisé dans une simple boucle..
- C'est exactement ce que je cherchais. Je ne savais pas qu'on l'appelle "la récursivité tail" en anglais. Un grand merci, camarade!
- Ou vous pouvez simplement mettre en œuvre une boucle en premier lieu, doh!
- la question est à propos rapide de la récursivité.
- Cette croît toujours en O(n), vous pouvez trouver O(log n) des algorithmes qui sont plus rapides nayuki.io/page/fast-fibonacci-algorithmes (lien dans les autres réponses)
- Deux ifs sont redondantes. Vous devez avoir soit une.
- merci de me montrer comment ce code pourrait ressembler à seul si
- Il suffit de supprimer la ligne et ça marche (pour n >= 1). ideone.com/1l4gCb
- Devrait-il être de retour fib(terme -1, val, val+prev)?
InformationsquelleAutor duedl0r
9

Ce genre de problèmes sont récurrence linéaire types et ils sont résolus, plus rapide via rapide des exponentielles de matrices. Voici la article sur le blog qui décrit ce type d'approche concise.

InformationsquelleAutor plesiv
7

Vous pouvez faire un peu plus vite que la version récursive de Fibonacci en utilisant memoization (ce qui signifie: stocker les résultats précédents afin d'éviter de recalculer eux). par exemple, voici une preuve de concept en Python, où un dictionnaire est utilisé pour l'enregistrement des résultats précédents:
```
results = { 0:0, 1:1 }

def memofib(n):
    if n not in results:
        results[n] = memofib(n-1) + memofib(n-2)
    return results[n]
```
Elle se retourne rapidement pour les valeurs d'entrée qui serait normalement bloquer la "normale", une version récursive. Il suffit de garder à l'esprit qu'une int type de données ne sera pas suffisant pour la tenue de grands résultats, et à l'aide de précision arbitraire des entiers est recommandé.

Une autre option tout - à réécrire cette version itérative ...
```
def iterfib(n):
    a, b = 0, 1
    for i in xrange(n):
        a, b = b, a + b
    return a
```
... comme une queue-fonction récursive, appelé loop dans mon code:
```
def tailfib(n):
    return loop(n, 0, 1)

def loop(i, a, b):
    if i == 0:
        return a
    return loop(i-1, b, a+b)
```
- J'ai mis à jour ma réponse avec une autre solution possible, pour info.
InformationsquelleAutor Óscar López

J'ai trouvé un article très intéressant sur fibonacci problème

ici l'extrait de code

# Returns F(n)
def fibonacci(n):
    if n < 0:
        raise ValueError("Negative arguments not implemented")
    return _fib(n)[0]


# Returns a tuple (F(n), F(n+1))
def _fib(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = _fib(n //2)
        c = a * (2 * b - a)
        d = b * b + a * a
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)

# added iterative version base on C# example
def iterFib(n):
    a = 0
    b = 1
    i=31
    while i>=0:
        d = a * (b * 2 - a)
        e = a * a + b * b
        a = d
        b = e
        if ((n >> i) & 1) != 0:
            c = a + b;
            a = b
            b = c
        i=i-1
    return a

Comment sur un processus itératif de version?
De l'article également inclus itératif version de C# nayuki.io/res/fast-fibonacci-algorithmes/fastfibonacci.cs

InformationsquelleAutor Moch Lutfi

2

Dites que vous voulez avoir le n-ième fib numéro, puis de construire un tableau contenant les précédents numéros de
```
int a[n];
a[0] = 0;
a[1] =1;
a[i] = n[i-1]+n[n-2];
```
- Il y a une solution sans stocker les valeurs dans un tableau. Si vous appelez f(n), chaque nombre (n, n-1, n-2, ..., 1, 0) sera calculé exactement une fois.
InformationsquelleAutor monkeyking

Un exemple en JavaScript qui utilise la récursivité et un initialisées cache pour une efficacité supplémentaire:

var cache = {};

function fibonacciOf (n) {
  if(n === 0) return 0;
  if(n === 1) return 1;
  var previous = cache[n-1] || fibonacciOf(n-1);
  cache[n-1] = previous;
  return previous + fibonacciOf(n-2);
};

InformationsquelleAutor Sebastian Sastre

duedl0r de l'algorithme traduit à Swift:

func fib(n: Int, previous: (Int, Int) = (0,1)) -> Int {
    guard n > 0 else { return 0 }
    if n == 1 { return previous.1 }
    return fib(n - 1, previous: (previous.1, previous.0 + previous.1))
}

travaillé exemple:

fib(4)
= fib(4, (0,1) )
= fib(3, (1,1) )
= fib(2, (1,2) )
= fib(1, (2,3) )
= 3

InformationsquelleAutor Ken Ko

0

Vous avez besoin de mémoriser la valeur calculée afin d'arrêter la croissance exponentielle.
1. Suffit d'utiliser un tableau pour stocker la valeur.
2. Vérifier le tableau si vous avez déjà calculer.
3. Si il le trouve,l'utiliser ou de le calculer et de le stocker.
Voici un exemple de travail pour accélérer la récursivité à l'aide de la mémoire.

Le calcul des nombres de fibonacci

InformationsquelleAutor kta

Un bon algorithme rapide de fibonacci calculs (en python):

def fib2(n):
    # return (fib(n), fib(n-1))
    if n ==  0: return (0,  1)
    if n == -1: return (1, -1)
    k, r = divmod(n, 2) # n=2k+r
    u_k, u_km1 = fib2(k)
    u_k_s, u_km1_s = u_k**2, u_km1**2  # Can be improved by parallel calls
    u_2kp1 = 4 * u_k_s - u_km1_s + (-2 if k%2 else 2)
    u_2km1 = u_k_s + u_km1_s
    u_2k   = u_2kp1 - u_2km1
    return (u_2kp1, u_2k) if r else (u_2k, u_2km1)

def fib(n):
    k, r = divmod(n, 2) # n=2k+r
    u_k, u_km1 = fib2(k)
    return (2*u_k+u_km1)*(2*u_k-u_km1)+(-2 if k%2 else 2) if r else u_k*(u_k+2*u_km1)

Si vous avez besoin de calcul très rapide, des liens vers la libgmp et l'utilisation mpz_fib_ui() ou mpz_fib2_ui fonctions ().

InformationsquelleAutor HNoob

Vous devez vous connecter pour publier un commentaire.