Hai công thức sau đều được sử dụng để tính số cách chọn k phần từ từ n phần tử sau: Theo em, trong hai công thức (2) và (3), công thức nào là công thức mang tính đệ quy? Em hãy giải thích c
2/9
Hai công thức sau đều được sử dụng để tính số cách chọn k phần từ từ n phần tử sau:
Theo em, trong hai công thức (2) và (3), công thức nào là công thức mang
tính đệ quy? Em hãy giải thích cho lựa chọn của mình.
Giải thích
Công thức 2 mang tính đệ quy
Sử dụng công thức ( 2 ) để tiếp tục quá trình tính toán, ta có F{n -1)- F(n - 2)+ F(n - 3), f( n - 2) = F(n - 3) + F(n - 4)... Do đó, nếu cứ gọi đến hàm F như vậy thÌ việc tính toán sẽ không có điểm dừng nên ta phải bỎ sang trường hợp đặc biệt được tính toán sẵn là hàm F tại n = 0 có giá trị 0 và tại n - 1 có giá trị 1. Công thức ( 2) là công thức mang tính đệ quy.