Bài 1: Đệ Quy Và Hàm Đệ Quy | Chuyên đề học tập Tin học 11 (Định hướng khoa học máy tính) | Chuyên Đề 1: Thực Hành Thiết Kế Thuật Toán Theo Kĩ Thuật Đệ Quy - Lớp 11 - Kết Nối Tri Thức Với Cuộc Sống

(Trang 5)

1. Khái niệm đệ quy

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.

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

(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

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.

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

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.

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.