HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV chia lớp thành các nhóm, yêu cầu thảo luận để hoàn thành Hoạt động 1 SGK trang 5:

Quan sát mô hình dãy số được tạo ra (Hình 1.4) và trả lời câu hỏi:

+ Dãy số được tạo ra theo quy luật nào?

+ Em hãy xác định hình và dãy số trong trường hợp n = 6.

- GV yêu cầu HS tìm hiểu khái niệm đệ quy trong sách, sau đó tìm hiểu thêm ví dụ khác từ thực tế để hiểu sâu hơn định nghĩa và ý nghĩa của khái niệm đệ quy. Tìm các ví dụ để thấy nếu không dùng định nghĩa đệ quy thì sẽ rất khó trình bày đúng về khái niệm đó.

- GV cho HS thảo luận cặp đôi, trả lời Câu hỏi để củng cố kiến thức:

+ Câu 1: Trường hợp nào sau đây không có tính chất đệ quy?

+ Câu 2: Phát biểu nào sau đây sai về đệ quy?

A. Một đối tượng được gọi là đệ quy nếu nó hoặc một phần của nó được định nghĩa thông qua khái niệm về chính nó.

B. Đối tượng đệ quy thì sự vật, hiện tượng liên quan đến đối tượng sẽ được lặp lại nhiều lần.

C. Trong đệ quy, lời giải của một bài toán phụ thuộc vào lời giải của các trường hợp nhỏ hơn cả cùng một bài toán.

D. Đệ quy là cách gọi khác của lặp.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS chia nhóm, thảo luận để trả lời Hoạt động 1 SGK trang 5.

- HS tìm hiểu khái niệm đệ quy và các ví dụ minh họa.

- HS làm việc nhóm đôi để trả lời Câu hỏi củng cố kiến thức.

- GV hướng dẫn, theo dõi, hỗ trợ HS khi cần.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện một số nhóm trình bày kết quả Hoạt động 1.

- HS xung phong phát biểu khái niệm đệ quy và nêu các ví dụ.

- GV gọi 1 - 2 HS trả lời Câu hỏi.

- GV mời HS nhóm khác nhận xét, bổ sung.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét, tổng kết, chuyển sang nội dung tiếp theo.

1. Khái niệm đệ quy

- Hoạt động 1:

+ Hình 1.4 là mô hình để tính tổng dãy số tự nhiên từ 1 đến k. Hình các ô vuông bước thứ k + 1 được thiết lập bằng cách bổ sung thêm phía dưới mẫu hình thứ k một hàng gồm k + 1 ô vuông (k = 1, 2,...)

→ tính chất của mẫu hình là bước sau có sử dụng lại mô hình của bước trước.

+ Hình và dãy số trong trường hợp n = 6 là:

f(6) = (1 + 2 + 3 + 4 + 5) + 6 = 21

       = f(5) + 6

- Khái niệm đệ quy: Khi một sự vật, hiện tượng có tính chất lặp lại chính nó hoặc được định nghĩa theo chính sự vật, hiện tượng đó thì được gọi là đệ quy.

- Ví dụ:

+ Dãy số tự nhiên có thể định nghĩa đơn giản như sau:

a) Số 0 là số tự nhiên.

b) Nếu n là số tự nhiên thì n + 1 cũng là số tự nhiên.

+ Dãy Fibonacci F(n) được định nghĩa đơn giản như sau:

a) F_­0 = 0, F₁ = 1

b) F_n = F_{n - 1} + F_{n - 2} với n > 1.

Câu hỏi:

Câu 1: Trường hợp D không có tính chất đệ quy.

Câu 2: Đáp án D sai.

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV chia lớp thành 3 nhóm, yêu cầu mỗi nhóm tìm hiểu một dãy số nổi tiếng để phát hiện các đặc điểm tương tự giữa các công thức này và khái niệm đệ quy.

+ Nhóm 1: Tìm hiểu dãy số Fibonacci

+ Nhóm 2: Tìm hiểu dãy số Lucas

+ Nhóm 3: Tìm hiểu dãy số Pell

- GV chốt kiến thức về công thức truy hồi của các dãy số truy hồi, từ đó nêu ra sự liên hệ với khái niệm đệ quy.

- GV yêu cầu HS giữ nguyên nhóm, tiếp tục thảo luận để hoàn thành các bài tập trong phần Câu hỏi nhằm khắc sâu kiến thức:

+ Câu 1: Em hãy xác định phần cơ sở và phần đệ quy của n!.

+ Câu 2: Em hãy xác định phần cơ sở và phần đệ quy của xⁿ.

Bước 2: HS thực hiện nhiệm vụ học tập

- Các nhóm HS tìm hiểu mỗi dãy số đã nêu trong SGK.

- HS thảo luận nhóm, hoàn thành bài tập phần Câu hỏi.

- GV theo dõi, hỗ trợ HS trong quá trình học tập.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện các nhóm trình bày kết quả thảo luận của nhóm mình.

- Đại diện các nhóm xung phong trả lời Câu hỏi.

- Các HS còn lại nhận xét, bổ sung (nếu có).

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét, bổ sung, tuyên dương ghi điểm các nhóm làm tốt.

- GV tổng kết lại nội dung.

- GV chuyển sang nội dung tiếp theo.

2. Công thức truy hồi

a) Dãy số Fibonacci

- Công thức:

+ Phần cơ sở: F_­0 = 0, F₁ = 1

+ Phần truy hồi: F_n = F_{n - 1} + F_{n - 2} với n > 1.

b) Dãy số Lucas

- Công thức:

+ Phần cơ sở: L_­0 = 2, L₁ = 1

+ Phần truy hồi: L_n = L_{n - 1} + L_{n - 2} với n > 1.

c) Dãy số Pell

- Công thức:

+ Phần cơ sở: P_­0 = 0, P₁ = 1

+ Phần truy hồi: P_n = 2P_{n - 1} + P_{n - 2} với n > 1.

→ Kết luận:

- Tất cả các công thức truy hồi đều có hai phần: phần cơ sở để xác định các giá trị ban đầu và phần truy hồi để tính các phần tử tiếp theo.

- Tất cả các dãy số được định nghĩa thông qua công thức truy hồi chính là được định nghĩa bằng khái niệm đệ quy.

Câu hỏi:

Câu 1:

- Phần cơ sở: 0! = 1, 1! = 1.

- Phần đệ quy: n! = n × (n - 1)!

Câu 2:

- Phần cơ sở: x⁰ = 1

- Phần đệ quy: xⁿ = x × x^{n - 1}

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV cho HS đọc bài toán trong Hoạt động 3 SGK trang 8, sau đó yêu cầu 2 HS lên bảng để thực hiện ngay trên máy tính hai chương trình đã ghi trong phần câu hỏi của hoạt động và chạy thử.

- GV yêu cầu các nhóm cùng trao đổi để tìm ra lỗi của hai chương trình này.

- GV cùng sửa hai chương trình để chương trình chạy hết lỗi.

- GV chốt kiến thức bằng cách mô tả cấu trúc tối thiểu phải có của các hàm đệ quy khi lập trình chạy trên máy tính.

- GV làm việc cá nhân, hoàn thành bài tập trong phần Câu hỏi nhằm củng cố kiến thức:

+ Câu 1: Trong chương trình tính số Fibonacci, các lệnh nào là phần cơ sở, các lệnh nào là phần đệ quy của chương trình?

+ Câu 2: Một hàm đệ quy sẽ có những thành phần nào?

A. Phần cơ sở và phần khởi tạo.

B. Phần cơ sở và phần đệ quy.

C. Phần đệ quy và phần khởi tạo.

Bước 2: HS thực hiện nhiệm vụ học tập

- Các nhóm HS tìm hiểu mỗi dãy số đã nêu trong SGK.

- HS thảo luận nhóm, hoàn thành bài tập phần Câu hỏi.

- GV theo dõi, hỗ trợ HS trong quá trình học tập.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện các nhóm trình bày kết quả thảo luận của nhóm mình.

- Đại diện các nhóm xung phong trả lời Câu hỏi.

- Các HS còn lại nhận xét, bổ sung (nếu có).

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét, bổ sung, tuyên dương ghi điểm các nhóm làm tốt.

- GV tổng kết lại nội dung.

- GV chuyển sang nội dung tiếp theo.

3. Hàm đệ quy

- Hoạt động 3: Cả hai chương trình An viết đều lỗi.

Chương trình 1:

+ Hàm của chương trình 1 sẽ bị lặp vô hạn lần → để sửa cần thêm các lệnh điều khiển dừng.

+ Sửa lại:

(Lưu ý: Các lệnh 5, 6 có thể có hoặc không.)

Chương trình 2:

+ Hàm có 2 lỗi: lỗi gọi đệ quy vô hạn không dừng và lỗi không thiết lập được các giá trị ban đầu của số Fibonacci với các trường hợp n = 0 và n = 1 → để sửa cần thêm các lệnh điều khiển dừng gọi đệ quy vô hạn và các lệnh thiết lập các giá trị ban đầu của dãy.

+ Sửa lại: Chương trình 2 có thể viết ngắn gọn hơn như sau:

- Kết luận: Cấu trúc tối thiểu phải có của các hàm đệ quy:

+ Phần gọi đệ quy.

+ Phần cơ sở: sẽ thiết lập các giá trị ban đầu của hàm và có vai trò kiểm soát, kết thúc các lời gọi đệ quy.

Câu hỏi:

Câu 1:

- Phần cơ sở: Các lệnh từ dòng 2 đến 5.

- Phần đệ quy: Các lệnh dòng 6, 7.

Câu 2: Câu B đúng.