An được giao tìm một thiết kế mới cho bài toán tính tổng S(n) có thể được viết lại như sau

Giải Chuyên đề Tin học 11 Kết nối tri thức Bài 2: Thiết kế thuật toán đệ quy

Khởi động trang 11 Chuyên đề Tin học 11: An được giao tìm một thiết kế mới cho bài toán tính tổng S(n) có thể được viết lại như sau:

S(n) = 1+2+3+…+n = 1+2+…+n-1+n = S(n-1)+n . Do đó, việc tính S(n) có thể được tính từ S(n-1), tương tự S(n-1) lại có thể được tính từ S(n-2). Cứ như vậy, cuối cùng sẽ dẫn đến cần tính S(0), nhưng S(0)=0. Em có thể giúp n hoàn thiện ý tưởng trên thành một chương trình hay không?

Hình 1. Máy tính ENIAC

Lời giải:

Bước 1. Bài toán yêu cầu tính tổng của n số nguyên từ 1 đến n. Cần thiết lập hàm S(n) trả về giá trị tổng cần tim.

Bước 2. Điều kiện n ≥ 0.

Với n = 0 ta có S(n) = 0. Đây là phần cơ sở cho điều kiện dừng của lời gọi đệ quy của hàm S(n).

Bước 3. Dễ thấy S(n) = n + S(n - 1) là công thức truy hồi của hàm S(n) và là cơ sở của lời gọi đệ quy của hàm. Chương trình như sau: