Recursive Functions Part 1

A recursive function is a function that calls itself. Each call solves a smaller version of the problem, until the problem is small enough to answer directly.

This function adds the whole numbers from 1 to n:

func sum_to_n(n: int) -> int:
	if n == 0: # base case
		return 0
	return n + sum_to_n(n - 1) # recursive step

It has two parts:

• The base case answers without calling the function again: the sum up to 0 is 0.
• The recursive step calls the function with a smaller value, n - 1, and builds its answer from the result.

sum_to_n(3) is 3 + sum_to_n(2), which is 3 + 2 + sum_to_n(1), which is 3 + 2 + 1 + sum_to_n(0). The base case returns 0, and the waiting calls finish one by one: the result is 6.

Every recursive step must move closer to the base case. Without a base case, or with a step like n + 1 that never reaches it, the function keeps calling itself. Godot allows about 1,000 calls inside each other and then stops the program with an error.