Giải chi tiết chuyên đề tin học định hướng Khoa học máy tính 11 Kết nối mới bài 1 Đệ quy và hàm đệ quy

Khởi động

Câu hỏi. Trong cuộc sống hằng ngày, các em thường gặp các hiện tượng sự vật, sự việc thể hiện giống hệt nhau, được lặp đi lặp lại với quy mô khác nhau. Ví dụ. búp bê Matryoshka rất nỗi tiếng của Nga. khi mở búp bê mẹ ra chúng ta lại thấy búp bê con bên trong. Lá dương xỉ có mỗi nhánh lá có cấu trúc giống cấu trúc tổng thể của lá. Cây súp lơ có mỗi nhánh của cây súp lơ là hình ảnh thu nhỏ của cả cây súp lơ.... Em có thể nói gì về đặc điểm chung nhất của các búp bê Matryoshka, lá dương xỉ và cây súp lơ?

 Hướng dẫn trả lời:

Đặc điểm chung nhất của các búp bê Matryoshka, lá cây dương xỉ và cây súp lơ là đều được định nghĩa dựa trên chính bản thân chúng. Được lặp đi lặp lại với quy mô khác nhau

1. Khái niệm đệ quy

Câu hỏi. 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:

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

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

Hướng dẫn trả lời:

1. Quy luật: Số đằng sau = số đằng trước + số thứ tự của nó

2.Với n = 6:

Hình như sau: Vẽ thêm một hàng có 6 ô ở dưới hình có n = 5

Dãy số: f(6) = (1 + 2 + 3 + 4 + 5) + 6 = 21 = f(5) + 6

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

Hướng dẫn trả lời:

• D. Ngôi sao

Câu hỏi 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ủa cùng một bài toán.

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

Hướng dẫn trả lời:

• 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ó.

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

Câu hỏi. Đọc, quan sát các công thức sau để 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.

Hướng dẫn trả lời:

• Tất cả các công thức truy hồi đều có hai phần: phần co 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 1. Em hãy xác định phần cơ sở và phần đệ quy của n!

Hướng dẫn trả lời:

• Phần cơ sở: P₀=1, P₁=1
• Phần đệ quy: P_n=n x (n - 1)!neun>1

Câu hỏi 2. Em hãy xác định phần cơ sở và phần đệ quy của thuật toán

Hướng dẫn trả lời:

• Phần cơ sở: P₀=1
• Phần đệ quy: P_n=XxX^n-1 neu n>0 XxXn−1x

3. Hàm đệ quy

Câu hỏi. Bạn An được yêu cầu viết các hàm đệ quy cho các bài toán sau:

1. Viết một hàm có chức năng in ra các số đếm ngược từ n xuống 1.

2. Viết hàm tính số Fibonacci thứ n.

Bạn An đã viết các hàm giải hai bài toán trên như Sau:

Chương trình 1.

1. def countdown(n):
2.           print(n)
3.           countdown(n        1)

Chương trình 2

1. def Fibonaccin(n):
2.         return Fibonaccin(n - 1) + Fibonaccin(n - 2)

Các hàm trên của bạn An có đúng không?

Hướng dẫn trả lời:

Các hàm của bạn An đều bị lỗi:

- Hàm của chương trình 1 sẽ bị lặp vô hạn lần. Như vậy, muốn sửa lỗi này cần có các lệnh điều khiển làm dừng quá trình gọi đệ quy. Các lệnh này được gọi là lệnh điều khiển dừng hay phần điều khiển dừng của hàm. Chương trình 1 được viết lại đúng sau khi thêm phần điều khiển dừng như sau:

1. def countdown(n):
2. if n>0
3.           print(n)
4.           countdown(n - 1)

- Chương trình 2 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. Như vậy, để sửa các lỗi này cần đưa vào 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. Các lệnh thiết lập các giá trị ban đầu của hàm với tham số đầu vào nhỏ sẽ được gọi là phần cơ sở của hàm đệ quy.

1. def Fibonaccin(n):
2. if n==0:
3.         return 0
4. elif n==1:
5.          return 1
6. else
7.         return Fibonaccin(n - 1) + Fibonaccin(n - 2)

Câu hỏi 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?

Hướng dẫn trả lời:

+ Phần cơ sở: F(w) = 0 nếu n = 0. F(n) = 1 nếu n > 1.

+ Phần đệ quy: F(n) = F (n - 1) + F(n - 2) nếu n >2

Câu hỏi 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.

Hướng dẫn trả lời:

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

Luyện tập 

Câu hỏi 1. Viết chương trình in và đếm xuôi từ 1 đến 100 trên màn hình.

Hướng dẫn trả lời:

Chương trình đệ quy Python để in và đếm từ 1 đến 100 trên màn hình có thể được viết như sau. Trong đó, hàm count được định nghĩa để in số và gọi lại chính nó với giá trị đầu vào tăng lên 1. Nếu giá trị đầu vào là 100 hoặc lớn hơn, hàm sẽ kết thúc đệ quy.

Chạy chương trình sẽ cho kết quả in ra các số từ 1 đến 100 trên màn hình.

1. def count(num):
2. if num <=100:
3.     print(num)
4.  count (num+1)
5. count(1)

Câu hỏi 2. Viết chương trình tính số Lucas thứ n.

Hướng dẫn trả lời:

Xác định phần cơ sở và phần đệ quy của chương trình tính số Fibonacci:

Phần cơ sở:  L₀=2,L₁=1

Phần đệ quy: L_n=L_n-1+L_n-2 neu n>1

Chương trình viết như sau

1. def lucas(n):
2. if n==0:
3. return 2
4.   elif n==1
5. return 1
6. else:
7. return lucas(n-1) + lucas(n-2)

Vận dụng

Câu hỏi 1. Viết chương trình nhập số n từ bàn phím và in ra n số hạng đầu tiên của dãy số Pell

Hướng dẫn trả lời:

Chương trình nhập số n từ bàn phím và in ra n số hạng đầu tiên của dãy số Pell:

1. def pell(n):
2. if n==1:
3. return 0
4.   elif n==2
5. return 1
6. else:
7. return 2*pell(n-1) + pell(n-2)
8. n- int(input("Nhập số n: ")
9. for i in range(1, n+1):
10. print(pell(i))

Câu hỏi 2. Viết chương trình tính số Pell thứ n.

Hướng dẫn trả lời:

1. def pell(n):
2. if n==1:
3. return 0
4.   elif n==2
5. return 1
6. else:
7. return 2*pell(n-1) + pell(n-2)