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ơ?

Giải chi tiết:

• Đượ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.

Giải chi tiết:

1. Dãy số được tạo theo quy luật: Fn = F(n-1) + n

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

• F6 = (1+2+3+4+5)+6 = F5 +6

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

Giải chi tiết:

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

Giải chi tiết:

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

Giải chi tiết:

• 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 1. Em hãy xác định phần cơ sở và phần đệ quy của n!

Giải chi tiết:

• Phần cơ sở: 1
• Phần truy hồi: n x (n - 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

Giải chi tiết:

• Phần cơ sở: 1
• Phần đệ quy: XxXⁿ⁻¹

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:

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

Giải chi tiế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.

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?

Giải chi tiết:

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

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.

Giải chi tiết:

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

Giải chi tiết:

Gợi ý:

i = 0

k = 1

while k <= 100:

i = i + 1

if i%10 == 0:

print (k)

else:

print (k, end = " ")

k = k + 1

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

Giải chi tiết:

Gợi ý:

#include <stdio.h>

#include <conio.h>

int Lucas(int n)

{

if (n == 1 || n == 2)

return 1;

return Lucas(n - 1) + Lucas(n - 2);

}

int main()

{

int n;

printf("nhap n: ");

scanf("%d", n);

printf("So Lucas thu %d la: %d", n, Lucas(n));

return 0;

}

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

Giải chi tiết:

uses crt;
Var a:array[1..100000] of longint;
i,n,min:longint;
Begin
clrscr;
write('Nhap n: '); readln(n);
For i:=1 to n do
Begin
Write('A[',i,'] = '); Readln(A[i]);
end;
for i:=1 to n do
if a[i]<min then min:=a[i];
write('Gia tri nho nhat trong day so vua nhap la: ',min);
readln
end.