Funções Recursivas Parte 1

Uma função recursiva é uma função que chama a si mesma. Cada chamada resolve uma versão menor do problema, até que o problema seja pequeno o suficiente para ser respondido diretamente.

Esta função soma os números inteiros de 1 até n:

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

Ele tem duas partes:

• O caso base responde sem chamar a função novamente: a soma até 0 é 0.
• A etapa recursiva chama a função com um valor menor, n - 1, e constrói sua resposta a partir do resultado.

sum_to_n(3) é 3 + sum_to_n(2), que é 3 + 2 + sum_to_n(1), que é 3 + 2 + 1 + sum_to_n(0). O caso base retorna 0, e as chamadas em espera terminam uma por uma: o resultado é 6.

Cada etapa recursiva deve se aproximar do caso base. Sem um caso base, ou com uma etapa como n + 1 que nunca o alcança, a função continua chamando a si mesma. Godot permite cerca de 1.000 chamadas aninhadas e, então, interrompe o programa com um erro.