Cho thuật toán:

Function Test(a,b): Integer;

Begin

If (b = a) or (b = 0) then Test:=1

Else Test := Test (a-1,b-1) + Test (a-1,b);

End;

Với a = 21, b = 3. Kết quả nào đúng trong số những kết quả dưới đây:

Để tìm kết quả của Test(21, 3), ta cần tính toán đệ quy theo định nghĩa của hàm. Hàm Test(a, b) được định nghĩa như sau: - Nếu b = a hoặc b = 0, thì Test(a, b) = 1 - Ngược lại, Test(a, b) = Test(a-1, b-1) + Test(a-1, b) Ta cần tính Test(21, 3): Test(21, 3) = Test(20, 2) + Test(20, 3) Test(20, 2) = Test(19, 1) + Test(19, 2) Test(20, 3) = Test(19, 2) + Test(19, 3) => Test(21, 3) = Test(19, 1) + 2*Test(19, 2) + Test(19, 3) Ta có thể nhận thấy rằng Test(a, b) thực chất là tổ hợp chập b của a, ký hiệu C(a, b) hay aCb. Công thức tính tổ hợp là C(n, k) = n! / (k! * (n-k)!). Trong trường hợp này, Test(a, b) tương ứng với C(a, b) nếu ta coi các điều kiện dừng b=a hoặc b=0 trả về 1, tương ứng C(a,a) = 1 và C(a,0) = 1. Vậy Test(21, 3) = C(21, 3) = 21! / (3! * 18!) = (21 * 20 * 19) / (3 * 2 * 1) = 7 * 10 * 19 = 1330. Do đó, đáp án đúng là 1330.