(Trang 5)
| Sau bài này em sẽ:
|
|
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ại 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ơ?
|
1. Khái niệm đệ quy
| Hoạt động 1 Làm quen với đệ quy Quan sát một mô hình dãy số được tạo ra (Hình 1.4) và trả lời câu hỏi:
Hình 1.4. Mô hình dãy số 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. |
n = 1
f(1) = 1
n = 2
f(2) = 1 + 2 = 3 = f(1) + 2
n = 3
f(3) = (1 + 2) + 3 = 6 = f(2) + 3
n = 4
f(4) = (1 + 2 + 3) + 4 = 10 = f(3) + 4
n = 5
f(5) = (1 + 2 + 3 + 4) + 5 = 15 = f(4) + 5
(Trang 6)
Hoạt động 1 là mô hình để tính tổng dãy số tự nhiên từ 1 đến n. Ta nhận thấy 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,...). Như vậy, 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.
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ì ta gọi là đệ quy. Trong thực tế có rất nhiều sự vật, hiện tượng được mô tả hoặc định nghĩa đệ quy. Chẳng hạn:
- Quan hệ “Họ hàng” có thể được định nghĩa như sau:
a) Bố, mẹ, anh, chị, em và các con của tôi là họ hàng của tôi.
b) Nếu một người là họ hàng của tôi thì bố, mẹ, anh, chị, em và các con của người đó sẽ là họ hàng của tôi.
- 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 số Fibonacci F(n) nổi tiếng được định nghĩa như sau:
a) F₀ = 0, F₁ = 1
b) Fₙ = Fₙ₋₁ + Fₙ₋₂ với n > 1.
Trong các ví dụ trên, ta thấy có điểm chung về định nghĩa một đối tượng, người ta sử dụng lại chính đối tượng đó.
Có thể hiểu một cách tổng quát khái niệm đệ quy như sau: Một khái niệm A được định nghĩa theo đệ quy nếu trong định nghĩa A có sử dụng ngay chính khái niệm А.
Khái niệm đệ quy được sử dụng rất nhiều trong cuộc sống, đặc biệt trong toán học và khoa học máy tính.
| 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. Các định nghĩa sử dụng đệ quy trong mô tả sự vật, khái niệm thường ngắn gọn và dễ hiều. |
1. Trường hợp nào sau đây không có tính chất đệ quy?
|
A. Tổ ong. |
B. Bắp cải. |
C. Lát cắt hành. |
D. Ngôi sao. |
(Trang 7)
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.
2. Công thức truy hồi
| Hoạt động 2 Tìm hiểu công thức truy hồi và các khái niệm liên quan đến đệ quy Đọ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. |
a) Dãy số Fibonacci
Dãy số Fibonacci được phát hiện từ rất lâu và hiện nay đã trở nên phổ biến ở khắp các lĩnh vực khác nhau của khoa học. Dãy được định nghĩa như sau:
a) F₀ = 0, F₁ = 1
b) Fₙ = Fₙ₋₁ + Fₙ₋₂ với n > 1.
Các đẳng thức a) được gọi là điều kiện ban đầu, hay cơ sở của dãy, công thức b) được gọi là công thức truy hồi (hay công thức đệ quy) của dãy. Một số phần tử ban đầu của dãy là: 0, 1, 1, 2, 3, 5, 8. Số Fibonacci có liên quan chặt chẽ đến khái niệm tỉ lệ vàng 
có nhiều ứng dụng thú vị trong toán học, nghệ thuật và trong đời sống.
b) Dãy số Lucas
Dãy số Lucas cũng rất nổi tiếng không chỉ vì nó rất gần với dãy số Fibonacci, mà ngay định nghĩa của dãy số này cũng giống Fibonacci. Dãy số Lucas được định nghĩa như sau:
a) L₀ = 2, L₁ = 1
b) Lₙ = Lₙ₋₁ + Lₙ₋₂ với n > 1.
Như vậy, chúng ta thấy công thức truy hồi của dãy số Lucas hoàn toàn giống với công thức truy hồi của dãy số Fibonacci, chỉ khác ở phần định nghĩa cơ sở. Một số phần tử ban đầu của dãy là: 2, 1, 3, 4, 7, 11.
(Trang 8)
c) Dãy số Pell
Dãy số Pell được định nghĩa như sau:
a) P₀ = 0, P₁ = 1.
b) Pₙ = 2Pₙ₋₁ + Pₙ₋₂ với n > 1.
Dãy số Pell gắn liền với cách tính gần đúng của 
. Dãy số này chính là dãy các mẫu số của dãy các phân số tối giản có giới hạn là: 1/1, 3/2, 7/5, 17/12, 41/29.
| 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. |
1. Em hãy xác định phần cơ sở và phần đệ quy của n!.
2. Em hãy xác định phần cơ sở và phần đệ quy của xⁿ.
3. Hàm đệ quy
| Hoạt động 3 Tìm hiểu và thiết lập hàm đệ quy 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 Fibonacci(n): 2 return Fibonacci(n - 1) + Fibonacci(n - 2) Các hàm trên của bạn An có đúng không? |
Nhận xét. Các hàm của bạn An viết đều có lệnh gọi đến chính mình, vậy đây là các hàm đệ quy. Tuy nhiên cả hai hàm trên đều lỗi.
(Trang 9)
– 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: <-- Lệnh điều khiển tiếp tục gọi đệ quy
3 print(n)
4 countdown(n - 1)
5 else: <-- Lệnh điều khiển dừng đệ quy
6 return
Lưu ý: Các lệnh 5, 6 có thể không có mà không ảnh hưởng đến việc điều khiển dừng đệ quy. Vậy chương trình trên có thể viết lại như sau, trong đó lệnh 2 sẽ đóng vai trò phần cơ sở của đệ quy.
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 dự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.
Chương trình 2 được sửa lại sau khi bổ sung các lệnh phần cơ sở và điều khiển dừng.
1 def Fibonacci(n):
2 if n >= 0:
Lệnh điều khiển tiếp tục gọi đệ quy
3 if n == 0:
4 return 0
5 elif n == 1:
Các lệnh thiết lập giá trị ban đầu của dãy Fibonacci
6 return 1
7 else:
8 return Fibonacci(n - 1) + Fibonacci(n - 2)
Lưu ý: Trên thực tế khi gọi hàm đệ quy Fibonacci(n), thông số n luôn được kiểm soát bên ngoài sao cho n ≥ 0 nên lệnh tại dòng 2 có thể bỏ đi. Với tham số đầu vào n ≥ 0 các lệnh thuộc phần cơ sở (từ dòng 3 đến dòng 6) có thêm vai trò điều khiển dừng của lời gọi đệ quy. Chương trình 2 có thể viết lại ngắn gọn hơn như sau:
(Trang 10)
1 def Fibonacci(n):
2 if n == 0:
3 return 0
4 elif n == 1:
5 return 1
6 else:
7 return Fibonacci(n - 1) + Fibonacci(n - 2)
Lệnh điều khiển dừng và các lệnh thuộc phần cơ sở được gọi chung là phần cơ sở của đệ quy. Như vậy, mỗi hàm hay thủ tục đệ quy đều phải có hai phần: phần gọi đệ quy và phần cơ sở có vai trò thiết lập các giá trị ban đầu của hàm và điều khiển dừng của đệ quy.
| Hàm hay thủ tục được gọi là đệ quy nếu có lời gọi đến chính mình. Mọi hàm đệ quy phải có phần gọi đệ quy và phần cơ sở. 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. |
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?
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.
LUYỆN TẬP
1. Viết chương trình in và đếm xuôi từ 1 đến 100 trên màn hình.
2. Viết chương trình tính số Lucas thứ n.
VẬN DỤNG
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.
2. Viết chương trình tính số Pell thứ n.
