Ricorsione in Java

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. Ricorsione in Java - 1

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:

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.

Un classico esempio di utilizzo di una funzione ricorsiva è il calcolo del fattoriale di un numero. Nel caso te ne fossi dimenticato, lascia che te lo ricordi: il fattoriale di un intero positivo 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:

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.

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 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. Se n = 0poi n! = 1. È necessario restituirlo 1.
Zero a qualsiasi potenza è uguale a zero.
Non considereremo l'incertezza del tipo 0^0e accetteremo tali dati di input come non validi.

Con tutti i controlli, i metodi saranno simili a questi:

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());
}

Commenti

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION