Hàm đệ quy phần 1

Hàm đệ quy là hàm tự gọi chính nó. Mỗi lần gọi giải quyết một phiên bản nhỏ hơn của bài toán, cho đến khi bài toán đủ đơn giản để trả lời trực tiếp.

Hàm này cộng các số nguyên từ 1 đến n:

func sum_to_n(n: int) -> int:
	if n == 0: # trường hợp cơ sở
		return 0
	return n + sum_to_n(n - 1) # bước đệ quy

Nó gồm hai phần:

• Trường hợp cơ sở đưa ra câu trả lời mà không gọi lại hàm: tổng đến 0 là 0.
• Bước đệ quy gọi hàm với giá trị nhỏ hơn, n - 1, rồi tạo câu trả lời từ kết quả đó.

sum_to_n(3) bằng 3 + sum_to_n(2), tức là 3 + 2 + sum_to_n(1), tức là 3 + 2 + 1 + sum_to_n(0). Trường hợp cơ sở trả về 0, các lời gọi đang chờ lần lượt hoàn tất: kết quả là 6.

Mỗi bước đệ quy phải tiến gần hơn đến trường hợp cơ sở. Nếu không có trường hợp cơ sở hoặc có một bước như n + 1 không bao giờ đạt tới trường hợp đó, hàm sẽ tiếp tục tự gọi chính nó. Godot cho phép khoảng 1.000 lần gọi lồng nhau, sau đó dừng chương trình và báo lỗi.