Recursione e Recursione Traccia in Kotlin

In questo articolo, imparerai a creare funzioni ricorsive. Una funzione che si chiama da sé. Inoltre, imparerai anche le funzioni ricorsive finali.

che si chiama da séfunzioneSi chiama funzione ricorsiva. E, questa tecnica si chiama ricorsione.

Un esempio fisico del mondo reale è posizionare due specchi paralleli uno di fronte all'altro. Qualsiasi oggetto tra di loro sarà riflettuto ricorsivamente.

Come funziona la ricorsione nel programming?

fun main(args: Array<String>) {
　　　　...　..　...
　　　　recurse()
　　　　...　..　...
}
fun recurse() {
　　　　...　..　...
　　　　recurse()
　　　　...　..　...
}

In questo caso, la chiamata alla funzione recurse() viene effettuata dal corpo della funzione recurse() stessa. Il funzionamento di questo programma è il seguente:

In questo caso, la chiamata ricorsiva continua per sempre, portando a una ricorsione infinita.

Per evitare la ricorsione infinita, è possibile utilizzare la ricorsione in una branca e non nella branca opposta.if ... else(o metodo simile).

Esempio: utilizzare la ricorsione per trovare il factorial di un numero

fun main(args: Array<String>) {
　　　　val number = 4
　　　　val result: Long
　　　　result = factorial(number)
　　　　println("$number!　=　$result")
}
fun factorial(n: Int): Long {}}
　　　　return if (n == 1) n.toLong() else n*factorial(n-1)
}

Quando si esegue questo programma, l'output è:

4!　=　24

Come funziona questo programma?

La seguente immagine di factorial() illustra le chiamate ricorsive della funzione:

Le fasi coinvolte sono le seguenti:

factorial(4)　//　Prima chiamata di funzione, parametro:　4
4*factorial(3)　//　Seconda chiamata di funzione, parametro:　3
4*(3*factorial(2))　//　Terza chiamata di funzione, parametro:　2
4*(3*(2*factorial(1)))　//　Quarta chiamata di funzione, parametro:　1　
4*(3*(2*1))　　　　　　　　　　　　　　　　　
24

Ricorsione tail call in Kotlin

La ricorsione tail call non è una caratteristica del linguaggio Kotlin, ma un concetto generale. Alcuni linguaggi di programmazione, inclusi Kotlin, lo utilizzano per ottimizzare le chiamate ricorsive, mentre altri linguaggi (ad esempio Python) non lo supportano.

Cos'è la ricorsione tail call?

Nella ricorsione normale, prima si eseguono tutte le chiamate ricorsive, poi si calcola il risultato in base ai valori di ritorno (come nell'esempio sopra). Quindi, prima di eseguire tutte le chiamate ricorsive, non si ottiene alcun risultato.

Nella ricorsione tail call, prima si esegue il calcolo, poi si esegue la chiamata ricorsiva (la chiamata ricorsiva passinga il risultato corrente alla prossima chiamata ricorsiva). Questo rende la chiamata ricorsiva equivalente a un ciclo, e evita il rischio di overflow della pila.

Condizioni della ricorsione tail call

Se la chiamata di funzione su se stesso è l'ultima operazione che esegue, la funzione ricorsiva può eseguire la ricorsione tail call. Ad esempio,

Esempio 1:Non soddisfa i requisiti della ricorsione tail call, poiché la chiamata di funzione su se stesso 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:Soddisfa le condizioni della ricorsione tail call, poiché 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 comunicare al compilatore di eseguire la ricorsione tail call in Kotlin, è necessario marcare la funzione con il modificador tailrec.

Esempio: Ricorsione tail call

import java.math.BigInteger
fun main(args: Array<String>) {
　　　　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 si esegue questo programma, l'output è:

354224848179261915075

Questo programma calcola il 100° termine della serie di Fibonacci. Poiché l'output può essere un numero intero molto grande, abbiamo importato la classe BigInteger dalla libreria standard di Java.

In questo caso, la funzione fibonacci() è marcata con il modificador trarec, la quale è qualificata per chiamate ricorsive tail call. Pertanto, il compilatore ha ottimizzato la ricorsione in questo caso.

Se cercate di trovare il 20000° termine della serie di Fibonacci (o qualsiasi altro grande numero intero) senza utilizzare la ricorsione tail call, il compilatore genererà l'eccezione java.lang.StackOverflowError.
Ma il nostro programma sopra è funzionato bene. Questo è perché abbiamo utilizzato la ricorsione tail call, che utilizza una versione efficiente basata su cicli, piuttosto che la ricorsione tradizionale.

Esempio: Calcolo del factorial con ricorsione tail call

Nell'esempio precedente (il primo esempio) l'esempio utilizzato per calcolare il factorial di un numero non può essere ottimizzato per la ricorsione tail call. Questo è un altro programma per eseguire la stessa attività.

fun main(args: Array<String>) {
　　　　val number = 5
　　　　println("$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 si esegue questo programma, l'output è:

5! = 120

Il compilatore può ottimizzare la ricorsione in questo programma perché le funzioni ricorsive possono eseguire la ricorsione traccia e abbiamo utilizzato il modificatore tailrec per informare il compilatore di ottimizzare la ricorsione.