Récursion Sur La Queue De Fibonacci

Comment puis-je mettre en œuvre une récursif de la fonction de Fibonacci avec aucune boucle exécute en O(n)?

Savez-vous comment obtenir le troisième nombre de Fibonacci? Quatrième? Cinquième?
"il faut un appel récursif de la fonction d'assistance" - quoi? Pourquoi? L'approche itérative est beaucoup plus facile. Je suppose qu'ils veulent une formulation récursive de la version itérative de la boucle.
Qu'est-ce que "n'est pas autorisé linéaire" censé signifier?
Désolé, ce sont juste les spécifications. Je ne peux pas utiliser les boucles, mais elle doit encore être linéaire.
L'astuce: retour de deux nombres, la dernière et la précédente.
Est-ce un devoir?
De retour de deux nombres de fibonacci.
que voulez-vous dire à propos de "pas de boucles d'exécution en O(n)" ????

InformationsquelleAutor Mat.S | 2014-03-01

48

Généralement, je serais contre le fait de poster une réponse à des devoirs à faire à la question comme ça, mais tout le posté jusqu'à présent semble être de compliquer à l'excès des choses. Comme dit dans les commentaires ci-dessus, vous devriez utiliser la récursivité pour résoudre le problème comme vous le feriez de manière itérative.

Voici la solution itérative:
```
def fib(n):
  a, b = 0, 1
  while n > 0:
    a, b = b, a+b
    n -= 1
  return a
```
Voici un équivalent solution récursive:
```
def fib(n):
  def fib_help(a, b, n):
    return fib_help(b, a+b, n-1) if n > 0 else a
  return fib_help(0, 1, n)
```
Noter que dans les deux cas, nous avons fait calculer jusqu'à F_n+1, mais le retour au F_n comme résultat. Cela correspond bien avec le "hint" vous avez été donné.

J'espère que vous prendrez le temps de comparer les deux solutions et vous convaincre qu'elles sont équivalentes. Comprendre comment transformer une solution itérative pour un équivalent récursive (ou vice versa) est une bonne compétence à développer.
- La queue forme récursive, hein? C'est une autre bonne façon de le faire. Compétence très utile dans le Schéma ou autres langages fonctionnels, et bon à savoir, juste pour le point de vue qu'il vous donne. Pas toujours le plus pratique transformation en Python, mais ni est la solution de l'indicateur de l'intention.
- Pas besoin de fib_help si vous donnez a et b de la fib en tant que paramètres par défaut: def fib(n, a=0, b=1): et return fib(n-1, b, a+b) if n > 0 else a
InformationsquelleAutor DaoWen

Scala code pour trouver de la n-ième Nombre de Fibonacci.
Pour plus d'informations sur la Queue de la Récursivité http://nerds.logdown.com/posts/1406258-n-th-fibonacci-number

object Main {
     def main(args: Array[String]) {
        println(fib(9));
        println(fib(8));
        println(fib(7));
        println(fib(6));
        println(fib(5));
        println(fib(4));
        println(fib(3));
        println(fib(2));
        println(fib(1));
        println(fib(0));
      }
      def fib(n: Int): Int = {
        def fib(n: Int, p :Int, c: Int): Int ={
          if (n == 0) return -1; // undefined
          if (n == 1) return p;
          fib(n-1, c, p + c)
        }
        fib(n, 0, 1);
      }
    }

InformationsquelleAutor Deepak Kumar

0

Pour résoudre ce dans le temps linéaire, vous devez utiliser une programmation dynamique technique connue sous le nom memoization.

L'algorithme de Fibonacci en pseudo-code, à l'aide de memoization, ressemble à ceci:
```
memoryMap[n]

func fib(int n)
    if (n is in memoryMap) then
        return memoryMap[n]
    if (n <= 1) then
        memoryMap[n] = n
    else
        memoryMap[n] = fib(n-1) + fib(n-2)

    return memoryMap[n]
```
D'expliquer, de vous après chaque appel à fib(x) - vous stocker le résultat dans une carte mémoire. Pour chaque appel ultérieur, toutes les recherches de fib(x) sera libre: c'est, en regardant le résultat dans la mémoire ne coûte que O(1) fois.
- C'est une façon de le faire, et la première qui vient à l'esprit pour moi aussi, mais pas le but de la solution. Combien d'une bonne ou une mauvaise chose, ce qui est une question d'opinion, mais si l'OP utilise, je recommande l'OP aussi la figure et de lui soumettre le but de la solution.
- La lecture de nouveau, il était évident que la bonne solution était une queue-de récursivité. Mais là encore, ça ne fonctionne toujours pas beaucoup de sens, que Python n'a même pas le soutien de la queue-elimination de la récursivité.
- Il est logique, même sans récursion sur la queue qu'elle utilise uniquement n appels récursifs qui doit tenir sur la pile pour fib. Comparez cela à de la naïveté de la récursivité fib(n) = fib(n-1) + fib(n-2) if n >1 else n
- Je sens que cette memoization est une chose naturelle à faire, afin d'éviter le calcul de choses plusieurs fois, vous enregistrez les résultats de calculs, quelque part, où vous pouvez consulter les résultats dans l'avenir. Il me semble que la qualifiant de "programmation dynamique", ajoute beaucoup de vapeur à quelque chose de très simple. Une version sans l'aide de mutation ou de missions serait intéressant.
InformationsquelleAutor 831

Au cas où quelqu'un est à la recherche d'une solution d'activer JavaScript:

function _fib(n, left, right) {
  switch (n) {
    case 0: return 0
    case 1: return right
    default: return _fib(n - 1, right, left + right)
  }
}

function fib(n) {
  return _fib(n, 0, 1)
}

Qui s'exécute en O(n) en temps et O(1) de l'espace avec la queue d'appel d'optimisation.

InformationsquelleAutor bcherny

Vous devez vous connecter pour publier un commentaire.