[Java] Numero attivazioni di un metodo ricorsivo

[Alhazred]

Ho scritto il codice ricorsivo per il calcolo del numero di Fibonacci, ora mi si chiede di aggiungere il conto del numero di attivazioni del metodo fibonacci(int n).
Il problema è che nella chiamata ricorsiva ci sono 2 invocazioni a tale metodo e come ho provato io vengono fuori dei casini.
Avete qualche idea su come risolvere la questione?

import javax.swing.JOptionPane;

public class Fibonacci {
   public static int fibonacci(int n) {
      if(n==0) return 0;
      else if(n==1) return 1;
      else return fibonacci(n-2)+fibonacci(n-1);
   }
   public static void main(String[] args) {
      int n = Integer.parseInt(JOptionPane.showInputDialog("Inserisci un valore per n"));
      int ris = fibonacci(n);
      System.out.println("Il valore risultante e': "+ris);
      System.exit(0);
   }
}

[Dav82]

Presumo che interessi vedere, alla fine, quante volte si è entrati nel metodo. Per questo basta mettere un attributo di classe (pure static, visto che ci devi accedere da un metodo static) da usare come contatore:

import javax.swing.JOptionPane;

private static int chiamate = 0;

public class Fibonacci {
   public static int fibonacci(int n) {
      chiamate ++;
      if(n==0) return 0;
      else if(n==1) return 1;
      else return fibonacci(n-2)+fibonacci(n-1);
   }
   public static void main(String[] args) {
      int n = Integer.parseInt(JOptionPane.showInputDialog
              ("Inserisci un valore per n"));
      int ris = fibonacci(n);
      System.out.println("Il valore risultante e': "+ris);
      System.exit(0);
   }
}

Calcolando F(5) avrai:

F(4): chiamate=1
  |--- F(2): chiamate=2
   |        |---- F(0): chiamate=3  //termina
   |        |---- F(1): chiamate=4  //termina
   |--- F(3): chiamate=5
            |---- F(1): chiamate=6 //termina
            |---- F(2): chiamate=7
                       |---- F(0): chiamate=8 //termina
                       |---- F(1): chiamate=9 //termina

chiamate = 9

O è da intendere in qualche altro modo?
Se per esempio ti interessa vedere solo il numero dei livelli finali, basta incrementare chiamate solo per n==0 o n==1.

Ciao

[Dav82]

Originariamente inviato da Dav82
Se per esempio ti interessa vedere solo il numero dei livelli finali, basta incrementare chiamate solo per n==0 o n==1.

Il mio cervello, durante il pranzo, mi ha fatto notare che contare il numero di livelli finali è un tantino da idiota, visto che è uguale al valore di n nella prima chiamata del metodo


C'è però, volendo, un altro aspetto da considerare: il valore di chiamate non funziona bene: se chiami prima fibonacci(5) e poi ancora fibonacci(4), alla seconda chiamata ti restituisce un numero sballato, e forse era proprio questo il tuo problema.
Potresti però aggirare il problema così: usi una variabile interna al metodo, e la poni a true se e solo se il valore di chiamate è pari a 0; alla fine del metodo poi controlli se sta variabile è true, e nel caso rimetti chiamate a 0.

import javax.swing.JOptionPane;

private static int chiamate = 0;

public class Fibonacci {

   public static int fibonacci(int n) {
      int result;
      boolean first = false;
      if (chiamate == 0)
         first = true;
      chiamate ++;
      if(n==0) result 0;
      else if(n==1) result 1;
      else result fibonacci(n-2)+fibonacci(n-1);
      (if first == true)
          chiamate = 0;
      return result;
   }

   public static void main(String[] args) {
      int n = Integer.parseInt(JOptionPane.showInputDialog
              ("Inserisci un valore per n"));
      int ris = fibonacci(n);
      System.out.println("Il valore risultante e': "+ris);
      System.exit(0);
   }
}

[Alhazred]

Con la soluzione del primo post funziona. Il fatto è che in un esempio il tutto veniva fatto aggiungendo un parametro al metodo e modifcando questo ad ogni invocazione. L'esempio però era su una ricorsione semplice, mentre questa è multipla e mi ha messo in difficoltà. Passando un parametro per tenere traccia del numero di attivazioni proprio non ho trovato soluzioni, ma magari in caso di ricorsioni multiple non è neanche fattibile.
Avevo fatto così:

import javax.swing.JOptionPane;
public class Fibonacci {
   public static int fibonacci(int n, int att) {
      att++;
      System.out.println("invocazione: "+att);
      if(n==0) return 0;
      else if(n==1) return 1;
      else return fibonacci(n-2,att)+fibonacci(n-1,att);
   }
   public static void main(String[] args) {
      int n = Integer.parseInt(JOptionPane.showInputDialog("Inserisci un valore per n"));
      int ris = fibonacci(n,0);
      System.out.println("Il valore risultante e': "+ris);
      System.exit(0);
   }
}

Ma ad esempio per n=4 ottengo come output:
1
2
3
3
2
3
3
4
4
Il valore risultante e': 3

[Dav82]

Al momento della chiamata della seconda ricorsione, dovresti poter avere accesso al valore di att calcolato nella prima, ma questo non lo puoi fare, perchè il valore che ti serve è una variabile interna del metodo fibonacci. Quindi l'unica cosa da fare è rendere questa variabile esterna al metodo, come nel mio esempio.

In C per esempio si potrebbe fare, passando le variabili per riferimento (qui invece si è costretti, per passare il riferimento - passami il termine - a usare una variabile globale).

[Alhazred]

Credo anch'io che sia l'unica soluzione.