Funciones recursivas, parte 1

Una función recursiva es una función que se llama a sí misma. Cada llamada resuelve una versión más pequeña del problema, hasta que el problema es lo suficientemente pequeño como para responderlo directamente.

Esta función suma los números enteros desde 1 hasta n:

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

Tiene dos partes:

• El caso base responde sin volver a llamar a la función: la suma hasta 0 es 0.
• El paso recursivo llama a la función con un valor menor, n - 1, y construye su respuesta a partir del resultado.

sum_to_n(3) es 3 + sum_to_n(2), que es 3 + 2 + sum_to_n(1), que es 3 + 2 + 1 + sum_to_n(0). El caso base devuelve 0, y las llamadas en espera terminan una por una: el resultado es 6.

Cada paso recursivo debe acercarse al caso base. Sin un caso base, o con un paso como n + 1 que nunca lo alcanza, la función sigue llamándose a sí misma. Godot permite unas 1.000 llamadas anidadas y luego detiene el programa con un error.