Ricorsione

La ricorsione è una tecnica di programmazione molto potente, che sfrutta l'idea di suddividere un problema da risolvere in sottoproblemi simili a quello originale, ma più semplici. Una funzione è detta ricorsiva se chiama se stessa. Se due funzioni si chiamano l’un l’altra, sono dette mutuamente ricorsive. Kotlin ha il supporto alla ricorsività, vediamo un esempio:

fun factorial(n: Long): Long = if (n == 0) 1 else n * factorial(n - 1)

fun main(args: Array<String>) {

println(factorial(10))

println(factorial(7))

}

Kotlin offre la keyword tailrec per scrivere una funzione ricorsiva senza il rischio di overflow dello stack. Quando una funzione viene contrassegnata con il modifacore tailrec il compilatore ottimizza la ricorsione, lasciando dietro una versione basata su un ciclo veloce ed efficiente. Questa keyword è molto utile in casi di funzioni che richiamano se stesse numerose volte:

tailrec fun findFixPoint(x: Double = 1.0): Double = if (x == Math.cos(x)) x else findFixPoint(Math.cos(x))

private fun findFixPoint(): Double {

var x = 1.0

while (true) {

val y = Math.cos(x)

if (x == y) return y

x = y

}

}

Senza la keyword tailrec la suddetta funzione rischia di andare in overflow dello stack. le due funzioni dello Snippet 3.30, in Kotlin, hanno una velocità di eseguzione e consumo di risorse molto simile. Non è possibile utilizzare la ricorsione se c'è del codice dopo la chiamata ricorsiva e non è possibile utilizzarla all'interno di try / catch / finally.