Thiết kế đệ quy cho bài toán tính tổng

Với $n$ nguyên không âm, cần tính $S(n)=1+2+\cdots+n$; khi $n=0$ thì tổng không có số hạng, bằng 0. Khi $n>0$, tách số hạng cuối để được $S(n)=n+S(n-1)$. Như vậy, thiết kế có ba ý: hàm trả tổng cần tìm; cơ sở là $S(0)=0$; trường hợp còn lại lấy $n$ cộng tổng của bài toán nhỏ hơn. ```python def tong(n): if n == 0: return 0 return n + tong(n - 1) ``` Đối số n−1 nhỏ hơn n và sẽ tới 0 khi bắt đầu bằng một số nguyên không âm. Không được giữ nguyên n trong lời gọi tiếp.

Gọi SL(n) là tổng các số tự nhiên lẻ không vượt quá n; đặt SL(n)=0 khi n≤0. Nếu n lẻ, cộng n vào kết quả nhỏ hơn. Nếu n chẵn, không cộng n nhưng vẫn giảm giới hạn. ```python def tong_le(n): if n <= 0: return 0 if n % 2 == 1: return n + tong_le(n - 1) return tong_le(n - 1) ``` Ví dụ tong_le(6)=tong_le(5)=5+3+1=9. Cả hai nhánh đều tiến về cơ sở; sự khác nhau nằm ở việc có cộng n hay không.