PDA

Visualizza versione completa : [Java] Numero attivazioni di un metodo ricorsivo


Alhazred
29-01-2005, 11.32.43
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
29-01-2005, 13.35.25
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
29-01-2005, 13.57.52
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 :p


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
29-01-2005, 14.42.06
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
29-01-2005, 14.48.58
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
29-01-2005, 15.00.59
Credo anch'io che sia l'unica soluzione.