In questo articolo imparerai a creare funzioni ricorsive; una funzione che chiama se stessa. Inoltre, imparerai a conoscere la funzione ricorsiva della coda.
Una funzione che chiama se stessa è nota come funzione ricorsiva. E questa tecnica è nota come ricorsione.
Un esempio del mondo fisico potrebbe essere quello di posizionare due specchi paralleli uno di fronte all'altro. Qualsiasi oggetto tra di loro verrebbe riflesso in modo ricorsivo.
Come funziona la ricorsione nella programmazione?
fun main (args: Array) (… recurse () …) fun recurse () (… recurse () …)
Qui, la recurse()funzione viene chiamata dal corpo della recurse()funzione stessa. Ecco come funziona questo programma:
Qui, la chiamata ricorsiva continua per sempre causando una ricorsione infinita.
Per evitare la ricorsione infinita, è possibile utilizzare if … else (o un approccio simile) dove un ramo effettua la chiamata ricorsiva e l'altro no.
Esempio: trova il fattoriale di un numero utilizzando la ricorsione
fun main(args: Array) ( val number = 4 val result: Long result = factorial(number) println("Factorial of $number = $result") ) fun factorial(n: Int): Long ( return if (n == 1) n.toLong() else n*factorial(n-1) )
Quando esegui il programma, l'output sarà:
Fattoriale di 4 = 24
Come funziona questo programma?
La chiamata ricorsiva della factorial()funzione può essere spiegata nella figura seguente:
Ecco i passaggi coinvolti:
fattoriale (4) // 1a chiamata di funzione. Argomento: 4 4 * fattoriale (3) // 2a chiamata di funzione. Argomento: 3 4 * (3 * fattoriale (2)) // 3a chiamata di funzione. Argomento: 2 4 * (3 * (2 * fattoriale (1))) // 4a chiamata di funzione. Argomento: 1 4 * (3 * (2 * 1)) 24
Ricorsione della coda di Kotlin
La ricorsione della coda è un concetto generico piuttosto che la caratteristica del linguaggio Kotlin. Alcuni linguaggi di programmazione, incluso Kotlin, lo usano per ottimizzare le chiamate ricorsive, mentre altri linguaggi (es. Python) non li supportano.
Cos'è la ricorsione della coda?
Nella ricorsione normale, si eseguono prima tutte le chiamate ricorsive e si calcola infine il risultato dai valori restituiti (come mostrato nell'esempio sopra). Quindi, non si ottengono risultati finché non vengono effettuate tutte le chiamate ricorsive.
Nella ricorsione in coda, i calcoli vengono eseguiti per primi, quindi vengono eseguite le chiamate ricorsive (la chiamata ricorsiva passa il risultato del passaggio corrente alla chiamata ricorsiva successiva). Ciò rende la chiamata ricorsiva equivalente al ciclo ed evita il rischio di overflow dello stack.
Condizione per la ricorsione della coda
Una funzione ricorsiva è idonea per la ricorsione in coda se la chiamata della funzione a se stessa è l'ultima operazione che esegue. Per esempio,
Esempio 1: non idoneo per la ricorsione in coda perché la chiamata di funzione a se stessa n*factorial(n-1)non è l'ultima operazione.
fun factorial (n: Int): Long (if (n == 1) (return n.toLong ()) else (return n * factorial (n - 1)))
Esempio 2: idoneo per la ricorsione in coda perché la chiamata di funzione a se stessa fibonacci(n-1, a+b, a)è l'ultima operazione.
fun fibonacci (n: Int, a: Long, b: Long): Long (return if (n == 0) b else fibonacci (n-1, a + b, a))
Per dire al compilatore di eseguire la ricorsione in coda in Kotlin, è necessario contrassegnare la funzione con un tailrecmodificatore.
Esempio: ricorsione della coda
import java.math.BigInteger fun main(args: Array) ( val n = 100 val first = BigInteger("0") val second = BigInteger("1") println(fibonacci(n, first, second)) ) tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger ( return if (n == 0) a else fibonacci(n-1, b, a+b) )
Quando esegui il programma, l'output sarà:
354224848179261915075
Questo programma calcola il 100 esimo termine della serie di Fibonacci. Poiché l'output può essere un numero intero molto grande, abbiamo importato la classe BigInteger dalla libreria standard Java.
Qui, la funzione fibonacci()è contrassegnata con un tailrecmodificatore e la funzione è idonea per la chiamata ricorsiva di coda. Quindi, il compilatore ottimizza la ricorsione in questo caso.
Se provi a trovare il 20000 esimo termine (o qualsiasi altro grande intero) della serie di Fibonacci senza usare la ricorsione in coda, il compilatore lancia java.lang.StackOverflowErrorun'eccezione. Tuttavia, il nostro programma sopra funziona perfettamente. È perché abbiamo utilizzato la ricorsione della coda che utilizza una versione basata su un ciclo efficiente invece della ricorsione tradizionale.
Esempio: fattoriale che utilizza la ricorsione della coda
L'esempio per calcolare il fattoriale di un numero nell'esempio precedente (primo esempio) non può essere ottimizzato per la ricorsione in coda. Ecco un programma diverso per eseguire la stessa operazione.
fun main(args: Array) ( val number = 5 println("Factorial of $number = $(factorial(number))") ) tailrec fun factorial(n: Int, run: Int = 1): Long ( return if (n == 1) run.toLong() else factorial(n-1, run*n) )
Quando esegui il programma, l'output sarà:
Fattoriale di 5 = 120
Il compilatore può ottimizzare la ricorsione in questo programma poiché la funzione ricorsiva è idonea per la ricorsione in coda, e abbiamo usato un tailrecmodificatore che dice al compilatore di ottimizzare la ricorsione.
