Ricorsione

Ogni linguaggio basato su funzioni supporta il concetto di ricorsione.
Ogni chiamata a funzione genera un nuovo push di stack frame e ogni ritorno ne causa il pop.

Uno stack frame è un ambito (scope) locale di variabili.

All'atto dell'uso una variabile viene ricercata a partire dal frame corrente e, se non trovata, la ricerca prosegue nei frame sottostanti.

Ad ogni pop di stack frame, quando cioè una funzione ritorna, le variabili locali ivi create rimangono orfane, ma non c'è bisogno di deallocarle esplicitamente, ci pensa il garbage collector.

Esempio

(160recursion.go):

package main

import "fmt"

// Ad ogni invocazione viene creato un nuovo stack frame
// return distrugge lo stack frame corrente
func fact(n int) int {
	if n == 0 {
		return 1
	}
	return n * fact(n-1)
}

func main() {
	fmt.Println(fact(7))
}

Evidentemente il numero di frame nello stack è finito, quindi una ricorsione troppo profonda ne può causare l'esaustione.

E' anche da notare che la ricorsione impone richieste di risorse notevoli. Solo alcuni problemi sono naturalmente risolvibili con ricorsione, in altri casi è conveniente pensare ad un algoritmo che usi iterazione.