Trong toán học, n giai thừa (kí hiệu n!) là tích của n số nguyên dương đầu tiên n!=n x (n-1) x …x 1. Vậy ta có thể dùng công thức sau đây để tính n! được không?

Trong phòng họp có người, mỗi người bắt tay lần lượt n - 1 người còn lại, giữa hai người bất kì chỉ bắt tay nhau đúng một lần. Em hãy:

a) Xác định số lượng cái bắt tay diễn ra trong phòng khi n = 0, 1, 2, 3, 4.

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.

Xét tập S được định nghĩa đệ quy như sau:

a) Phần cơ sơ: 3 là phần từ của S.

b) Phần đệ quy: Nếu x thuộc S và y thuộc S thì x + y thuộc S (chú ý: x và y có thể có cùng giá trị).

Em hãy liệt kê 10 phần tử của tập S

Kí hiệu tập hợp tất cả các số nguyên dương lẻ là S. Em hãy:

a) Đưa ra định nghĩa đệ quy cho tập S.

b) So sánh cách mô tả tập S sử dụng định nghĩa đệ quy mà em xây dựng được ở câu a) với hai cách sau đây:

Cách liệt kê các phân tử: S = {1, 3, 5, 7, 9....}

Cách sử dụng mệnh để logic: S = {x | x ∈ N*, x không chia hết cho 2}.

Hàm đem Bupbe (búp bê A) ở Hình 3 được sử dụng để mô tả cách đếm số búp bê của bộ Matryoshka một cách đệ quy nếu búp bê A là búp bê lớn nhất của bộ. Em hãy cho biết dấu (?) trong hàm dem_Bupbe (búp bê A) cần được thay bằng gì.

b) Đưa ra định nghĩa đệ quy cho hàm h(n) tính số lượng cái bắt tay đã diễn ra trong phòng có n người.

Gợi ý: Để xây dựng phân đệ quy cho h(n), em hãy xác định lời giải của bài toán khi có 0 người trong phòng từ lời giải của bài toán khi có n - 1 người trong phòng.