Per capire cos'è la ricorsione, è necessario capire cos'è la ricorsione. In effetti, non c'è niente di difficile nel comprendere tali funzioni, basta capirle bene una volta sola. E fai pratica quando si tratta di programmazione. La ricorsione avviene non solo nella programmazione, ma anche nella vita reale. Prendi uno specchio tra le mani e mettiti di fronte a un altro specchio. Il riflesso del riflesso si rifletterà nel riflesso e così via. Vedrai un numero infinito di riflessi che vanno all'infinito. Puoi trovare di più sulla ricorsione “reale” nell'articolo “ Dedicato a Ricomincio da capo... ” Torniamo dal mondo reale alla vita quotidiana di un programmatore. Definizione semplice: le funzioni ricorsive in Java sono funzioni che chiamano se stesse. Lascia che ti faccia un esempio molto semplice e molto dannoso:
Qual è il vantaggio di un metodo rispetto ad un altro? Non sembra che ci sia una grande differenza, ma in realtà molte chiamate ricorsive avranno un impatto negativo sulle prestazioni e sul consumo di memoria: lo stack di chiamate è una risorsa quasi incontrollabile e in condizioni diverse per chiamare la stessa funzione ricorsiva, potremmo riscontrare o meno problemi associati a questa risorsa. Quasi tutti i problemi risolti utilizzando iterazioni (cicli come
public void recursionFucn() {
System.out.println("Привет, JavaRush!");
recursionFucn();
}
Perché è dannoso? Ti consiglio di verificarlo tu stesso! Se decidi di intraprendere questa avventura (e molto probabilmente lo farai, programmatore!), scrivi nei commenti quale errore lancerà la JVM =) Questo esempio, e molti altri, dimostrano che l'uso della ricorsione in Java deve essere affrontato con attenzione . Devi capire dove, quando e perché un simile approccio alla risoluzione di un problema è giustificato e assicurarti che la tua funzione non trasformi l'esecuzione del programma in "Ricomincio da capo". Esistono due definizioni più importanti per comprendere la ricorsione:
- Base di ricorsione - la condizione per uscire dal blocco delle chiamate ricorsive - la soluzione di base al problema, in condizioni in cui non è necessario chiamare la ricorsione.
- Il passo di ricorsione avviene quando una funzione richiama se stessa quando si modificano i parametri.
N
(indicato come N!) è il prodotto dei numeri da 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N
. A proposito, il fattoriale di zero per definizione è uguale a 1. Quindi il fattoriale può essere trovato per qualsiasi numero intero positivo e zero (nel linguaggio della matematica - per l'insieme di numeri interi non negativi o per l'insieme di numeri naturali e zero). Penso che tu capisca che puoi programmare il fattoriale usando i loop. In realtà, ecco un metodo non ricorsivo per risolvere questo problema:
private int fact(int n) {
int result = 1;
for (int i = 1; i <= n; i++) {
result = result * i;
}
return result;
}
Aggiungiamo un controllo che il numero sia positivo e un numero intero e un controllo separato per zero.
private int fact(int n) {
if (n < 0) {
System.out.println("Зачем тебе факториал из отрицательного числа?");
return null;
}
int result = 1;
if (n == 0) {
return result;
}
for (int i = 1; i <= n; i++) {
result = result * i;
}
return result;
}
Ora fornirò il codice del metodo per risolvere ricorsivamente questo problema:
private int factorial(int n) {
int result = 1;
if (n == 1 || n == 0) {
return result;
}
result = n * factorial(n-1);
return result;
}
Diamo un'occhiata ai risultati di output per le chiamate:
System.out.println(factorial(0));
System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(3));
System.out.println(factorial(4));
System.out.println(factorial(5));
System.out.println(factorial(6));
Otteniamo i valori attesi:
1
1
2
6
24
120
720
Aggiungiamo un bel output e calcoliamo il fattoriale per un numero maggiore:
private int factorial(int n) {
int result = 1;
if (n == 0) {
System.out.print(" = ");
return result;
}
if (n == 1) {
System.out.print(" * 1 = ");
return result;
}
System.out.print(n);
if (n != 2) {
System.out.print(" * ");
}
result = n * factorial(n-1);
return result;
}
System.out.println(factorial(15) + "!");
Otteniamo: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000!
In questo caso l'uso di una funzione ricorsiva è giustificato e sicuro. Abbiamo definito chiaramente la condizione per uscire dal blocco ricorsivo, e siamo certi che sia realizzabile: inseriamo un numero intero non negativo, se il numero è uguale a zero o uno, restituiamo il risultato, se il numero è maggiore , moltiplichiamo il risultato per una funzione del numero n-1
. Usando il fattoriale di tre come esempio:
factorial(3) внутри себя выполнит следующее:
result = 3 * factorial(2); (рекурсивный вызов)
factorial(2) внутри себя выполнит следующее:
result = 2 * factorial(1); (рекурсивный вызов)
factorial(1) вернет 1 (базис рекурсии)
factorial(2) вернет 2 * 1
factorial(3) вернет 3 * 2 * 1
Per quanto riguarda la cautela nell'uso: qual è la vulnerabilità di questa funzione? Se assegni a un metodo un numero negativo come parametro, allora check
if (n == 1 || n == 0) {
return result;
}
non ha senso e finiremo in un ciclo infinito di autodefinizione. Vale la pena aggiungere un controllo di non negatività:
if (n < 0) {
System.out.println(«Зачем тебе факториал отрицательного числа?»);
return null;
}
E tutto andrà bene.
for-each
) possono essere risolti anche ricorsivamente. Il vantaggio della ricorsione è la leggibilità e la facilità di scrittura, degli svantaggi abbiamo parlato sopra: la possibilità di “darsi la zappa sui piedi” non è illusoria. Bisogna prestare ancora più attenzione quando si utilizza la cosiddetta “ricorsione complessa": una funzione A()
chiamerà una funzione B()
che chiama una funzione A()
. Per risolvere tali problemi è necessaria una piena comprensione di come funziona la ricorsione. Un esempio di tale compito: calcolare il valore di x^n/(n!)
. Il fattoriale, come abbiamo discusso sopra, è definito sull'insieme degli interi non negativi. Infine, fornirò il codice della soluzione. La ricorsione complessa consisterà di due metodi:
private double calculate(int x, int n) {
return power(x, n) / n;
}
private double power(int x, int n) {
if (n == 1) return x;
return x * calculate(x, n - 1);
}
Per accedere alla ricorsione, viene utilizzato un metodo calculate
, che chiama un metodo power
, che a sua volta chiama un metodo calculate
. Abbiamo definito la base ricorsiva nel metodo delle potenze:
if (n == 1) return x;
Anche il passo di ricorsione è definito qui:
return x * calculate(x, n - 1);
Resta da aggiungere un controllo sulla validità dei dati di input:
- Qualsiasi numero diverso da zero è uguale alla potenza di zero
1
. Sen = 0
poin! = 1
. È necessario restituirlo1
. - Zero a qualsiasi potenza è uguale a zero.
- Non considereremo l'incertezza del tipo
0^0
e accetteremo tali dati di input come non validi.
private double calculate(int x, int n) throws ArithmeticException {
if (x == 0 && n == 0) {
throw new ArithmeticException("Невалидные входные данные: Неопределенность типа 0^0");
}
if (n < 0) {
throw new ArithmeticException("Невалидные входные данные: Факториал из отрицательного числа!");
}
if (n == 0) {
return 1;
}
if (x == 0) {
return 0;
}
if (x == 0) {
return 0;
}
return power(x, n) / n;
}
private double power(int x, int n) {
if (n == 1) return x;
return x * calculate(x, n - 1);
}
Bene, quando chiami una funzione devi ricordarti di rilevare l'errore:
try {
System.out.println(calculate(x, n));
} catch (ArithmeticException e) {
System.out.println(e.getMessage());
}
GO TO FULL VERSION