Dans le programme de fibonacci récursif pourquoi le sous-arbre gauche est appelé avant le droit (quelque chose comme la traversée postorder)?

Question

package fibonacci; 

public class Fib { 

    static int fib(int n) 
    { 
     System.out.println("fib(" + n + ") called"); 
     if(n<=1) 
     { 
      return n; 
     } 
     int temp = fib(n-1) + fib(n-2); 
     System.out.println("returning to fib(" + n +")"); 
     return temp; 
    } 
    public static void main(String[] args) 
    { 
     System.out.println("fib(5): " + fib(5)); 
    } 
} 

---

sortie:

fib (5) appelé
fib (4) appelé
fib (3) appelé
fib (2) appelé
fib (1) appelé
fib (0) appelé
retournant à fib (2)
fib (1) appelé
revenant à fib (3)
fib (2) appelé
fib (1) appelé
fib (0) appelée
retour à fib (2)
retour à fib (4)
fib (3) appelé
fib (2) appelé
fib (1) appelé
fib (0) appelée
retour à fib (2)
fib (1) appelé
retour à fib (3)
retour à fib (5
fib (5): 5

PS: Pourquoi fib (n-1) est appelé avant fib (n-2)?

Answer 1

Ceci peut être expliqué par le following section of JLS -

Les garanties de langage de programmation Java que les opérandes de opérateurs semblent être évalués dans un ordre d'évaluation spécifique, à savoir de gauche à droite.

Dans votre cas, l'opérande gauche est l'appel à fib(n-1), il sera évalué en profondeur pour calculer la valeur finale, et alors seulement la bonne opération sera évaluée.

Answer 2

Parce que la première partie qui est exécutée, est appelé en premier, par exemple si vous le ceci:

void dfs(int x) { 
    dfs(x-1); 
    dfs(x-2); 
} 

Puis DSF (x-1) sera appelé d'abord, ainsi DSF seront appelés à nouveau, et le DAM (x-1) sera appelé une fois de plus parce que c'est la première instruction et ainsi de suite jusqu'à ce que dfs (x-1) soit appelé alors le programme continue avec dfs (x-2).

J'espère que ça aide.