Funzioni ricorsive - Parte 1

Una funzione ricorsiva è una funzione che richiama sé stessa. Ogni chiamata risolve una versione più semplice del problema, finché il problema non è abbastanza semplice da poter ricevere una risposta diretta.

Questa funzione somma i numeri interi da 1 a n:

func sum_to_n(n: int) -> int:
	if n == 0: # caso base
		return 0
	return n + sum_to_n(n - 1) # passo ricorsivo

Ha due parti:

• Il caso base risponde senza richiamare la funzione: la somma fino a 0 è 0.
• Il passo ricorsivo richiama la funzione con un valore più piccolo, n - 1, e costruisce la risposta a partire dal risultato.

sum_to_n(3) è 3 + sum_to_n(2), che è 3 + 2 + sum_to_n(1), che è 3 + 2 + 1 + sum_to_n(0). Il caso base restituisce 0 e le chiamate in attesa terminano una alla volta: il risultato è 6.

Ogni passaggio ricorsivo deve avvicinarsi al caso base. Senza un caso base, o con un passaggio come n + 1 che non lo raggiunge mai, la funzione continua a chiamare sé stessa. Godot consente circa 1.000 chiamate annidate e poi arresta il programma con un errore.