Đệ quy là một mẫu lập trình hữu ích trong các tình huống khi một tác vụ có thể được chia thành nhiều tác vụ cùng loại nhưng đơn giản hơn. Hoặc khi một nhiệm vụ có thể được đơn giản hóa thành một hành động dễ dàng cộng với một biến thể đơn giản hơn của cùng một nhiệm vụ. Hoặc, như chúng ta sẽ sớm thấy, để xử lý các cấu trúc dữ liệu nhất định
Khi một hàm giải quyết một tác vụ, trong quá trình đó, nó có thể gọi nhiều hàm khác. Một phần trường hợp này là khi một hàm gọi chính nó. Đó gọi là đệ quy
Hai cách suy nghĩ
Đối với một cái gì đó đơn giản để bắt đầu – hãy viết một hàm
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
8 nâng function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
9 lên lũy thừa tự nhiên của function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
0. Nói cách khác, nhân function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
9 với chính nó function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
0 lầnpow[2, 2] = 4
pow[2, 3] = 8
pow[2, 4] = 16
Có hai cách để thực hiện nó
suy nghĩ lặp đi lặp lại. vòng lặp
3function pow[x, n] { if [n == 1] { return x; } else { return x * pow[x, n - 1]; } } alert[ pow[2, 3] ]; // 8
function pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
tư duy đệ quy. đơn giản hóa nhiệm vụ và tự gọi
function pow[x, n] { if [n == 1] { return x; } else { return x * pow[x, n - 1]; } } alert[ pow[2, 3] ]; // 8
Xin lưu ý cách biến thể đệ quy khác nhau về cơ bản
Khi
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
8 được gọi, quá trình thực thi sẽ chia thành hai nhánhfunction pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
0- Nếu
5, thì mọi thứ đều tầm thường. Nó được gọi là cơ sở của đệ quy, bởi vì nó ngay lập tức tạo ra kết quả rõ ràng.function pow[x, n] { if [n == 1] { return x; } else { return x * pow[x, n - 1]; } } alert[ pow[2, 3] ]; // 8
6 bằngfunction pow[x, n] { if [n == 1] { return x; } else { return x * pow[x, n - 1]; } } alert[ pow[2, 3] ]; // 8
9function pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
- Nếu không, chúng ta có thể đại diện cho
8 làfunction pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
9. Trong môn toán, người ta sẽ viếtfunction pow[x, n] { if [n == 1] { return x; } else { return x * pow[x, n - 1]; } } alert[ pow[2, 3] ]; // 8
00. Đây được gọi là bước đệ quy. chúng tôi chuyển đổi tác vụ thành một hành động đơn giản hơn [nhân vớifunction pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
9] và một lệnh gọi đơn giản hơn cho cùng một tác vụ [function pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
02 vớifunction pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
0 thấp hơn]. Các bước tiếp theo đơn giản hóa nó ngày càng nhiều cho đến khifunction pow[x, n] { if [n == 1] { return x; } else { return x * pow[x, n - 1]; } } alert[ pow[2, 3] ]; // 8
0 đạt đếnfunction pow[x, n] { if [n == 1] { return x; } else { return x * pow[x, n - 1]; } } alert[ pow[2, 3] ]; // 8
05function pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
Chúng ta cũng có thể nói rằng
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
02 tự gọi đệ quy cho đến khi function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
5Ví dụ: để tính toán
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
08, biến thể đệ quy thực hiện các bước sau
09function pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
60function pow[x, n] { if [n == 1] { return x; } else { return x * pow[x, n - 1]; } } alert[ pow[2, 3] ]; // 8
61function pow[x, n] { if [n == 1] { return x; } else { return x * pow[x, n - 1]; } } alert[ pow[2, 3] ]; // 8
62function pow[x, n] { if [n == 1] { return x; } else { return x * pow[x, n - 1]; } } alert[ pow[2, 3] ]; // 8
Vì vậy, đệ quy rút gọn lời gọi hàm thành một lời gọi đơn giản hơn, và sau đó – thành đơn giản hơn nữa, v.v., cho đến khi kết quả trở nên rõ ràng
Đệ quy thường ngắn hơn
Một giải pháp đệ quy thường ngắn hơn một giải pháp lặp lại
Ở đây chúng ta có thể viết lại tương tự bằng cách sử dụng toán tử điều kiện
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
63 thay vì function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
64 để làm cho function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
8 ngắn gọn hơn và vẫn rất dễ đọcfunction pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
6Số lần gọi lồng nhau tối đa [bao gồm cả cuộc gọi đầu tiên] được gọi là độ sâu đệ quy. Trong trường hợp của chúng tôi, nó sẽ chính xác là
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
0Độ sâu đệ quy tối đa bị giới hạn bởi công cụ JavaScript. Chúng ta có thể dựa vào đó là 10000, một số công cụ cho phép nhiều hơn, nhưng 100000 có thể vượt quá giới hạn đối với phần lớn trong số chúng. Có các tối ưu hóa tự động giúp giảm bớt điều này [“tối ưu hóa cuộc gọi đuôi”], nhưng chúng chưa được hỗ trợ ở mọi nơi và chỉ hoạt động trong các trường hợp đơn giản
Điều đó hạn chế việc áp dụng đệ quy, nhưng nó vẫn còn rất rộng. Có nhiều tác vụ mà cách suy nghĩ đệ quy cho mã đơn giản hơn, dễ bảo trì hơn
Bối cảnh thực thi và ngăn xếp
Bây giờ hãy kiểm tra xem các cuộc gọi đệ quy hoạt động như thế nào. Đối với điều đó, chúng ta sẽ xem xét các chức năng
Thông tin về quá trình thực hiện chức năng đang chạy được lưu trữ trong ngữ cảnh thực thi của nó
Bối cảnh thực thi là một cấu trúc dữ liệu nội bộ chứa các chi tiết về việc thực thi một chức năng. vị trí hiện tại của luồng điều khiển, các biến hiện tại, giá trị của
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
67 [chúng tôi không sử dụng nó ở đây] và một số chi tiết nội bộ khácMột lệnh gọi hàm có chính xác một ngữ cảnh thực thi được liên kết với nó
Khi một chức năng thực hiện cuộc gọi lồng nhau, điều sau đây sẽ xảy ra
- Chức năng hiện tại bị tạm dừng
- Bối cảnh thực thi được liên kết với nó được ghi nhớ trong một cấu trúc dữ liệu đặc biệt được gọi là ngăn xếp bối cảnh thực thi
- Cuộc gọi lồng nhau thực hiện
- Sau khi nó kết thúc, bối cảnh thực thi cũ được lấy ra từ ngăn xếp và chức năng bên ngoài được tiếp tục từ nơi nó dừng lại
Hãy xem điều gì xảy ra trong cuộc gọi
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
68bột [2, 3]
Khi bắt đầu cuộc gọi
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
68, bối cảnh thực thi sẽ lưu trữ các biến. function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
70, luồng thực thi nằm ở dòng function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
05 của hàmChúng ta có thể phác họa nó như
- Bối cảnh. { x. 2, n. 3, tại dòng 1 } pow[2, 3]
Đó là khi chức năng bắt đầu thực thi. Điều kiện
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
5 là sai, vì vậy luồng tiếp tục vào nhánh thứ hai của function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
64function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
7Các biến giống nhau, nhưng dòng thay đổi, vì vậy bối cảnh bây giờ là
- Bối cảnh. { x. 2, n. 3, ở dòng 5 } pow[2, 3]
Để tính toán
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
9, chúng ta cần tạo một lớp con của ________ 102 với các đối số mới _______ 376bột [2, 2]
Để thực hiện lệnh gọi lồng nhau, JavaScript ghi nhớ ngữ cảnh thực thi hiện tại trong ngăn xếp ngữ cảnh thực thi
Ở đây chúng ta gọi hàm tương tự là
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
02, nhưng nó hoàn toàn không thành vấn đề. Quá trình này là giống nhau cho tất cả các chức năng- Bối cảnh hiện tại được "ghi nhớ" trên đầu ngăn xếp
- Bối cảnh mới được tạo cho subcall
- Khi cuộc gọi phụ kết thúc - bối cảnh trước đó được bật ra khỏi ngăn xếp và quá trình thực thi của nó tiếp tục
Đây là ngăn xếp ngữ cảnh khi chúng tôi tham gia cuộc gọi phụ
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
76- Bối cảnh. {x. 2, n. 2, tại dòng 1 } pow[2, 2]
- Bối cảnh. { x. 2, n. 3, ở dòng 5 } pow[2, 3]
Bối cảnh thực thi hiện tại mới ở trên cùng [và được in đậm] và các bối cảnh được ghi nhớ trước đó ở bên dưới
Khi chúng tôi kết thúc cuộc gọi phụ - thật dễ dàng để tiếp tục bối cảnh trước đó, bởi vì nó giữ cả hai biến và vị trí chính xác của mã nơi nó dừng lại
Xin lưu ý
Ở đây trong hình, chúng tôi sử dụng từ “dòng”, vì trong ví dụ của chúng tôi, chỉ có một lệnh gọi phụ trong dòng, nhưng nhìn chung một dòng mã có thể chứa nhiều lệnh gọi phụ, chẳng hạn như
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
79Vì vậy, sẽ chính xác hơn khi nói rằng quá trình thực thi sẽ tiếp tục “ngay sau cuộc gọi phụ”
bột [2, 1]
Quá trình lặp lại. một cuộc gọi phụ mới được thực hiện tại dòng
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
80, bây giờ với các đối số function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
81, function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
82Một bối cảnh thực thi mới được tạo, bối cảnh trước đó được đẩy lên trên cùng của ngăn xếp
- Bối cảnh. {x. 2, n. 1, tại dòng 1 } pow[2, 1]
- Bối cảnh. {x. 2, n. 2, ở dòng 5 } pow[2, 2]
- Bối cảnh. { x. 2, n. 3, ở dòng 5 } pow[2, 3]
Hiện có 2 ngữ cảnh cũ và 1 ngữ cảnh hiện đang chạy cho
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
83Lối thoát
Trong quá trình thực hiện của
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
83, không giống như trước đây, điều kiện của function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
5 là đúng nên nhánh đầu tiên của function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
64 hoạt độngfunction pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
8Không còn lệnh gọi lồng nhau nào nữa, vì vậy hàm kết thúc, trả về
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
87Khi chức năng kết thúc, bối cảnh thực thi của nó không còn cần thiết nữa, do đó, nó sẽ bị xóa khỏi bộ nhớ. Cái trước đó được khôi phục khỏi đỉnh ngăn xếp
- Bối cảnh. {x. 2, n. 2, ở dòng 5 } pow[2, 2]
- Bối cảnh. { x. 2, n. 3, ở dòng 5 } pow[2, 3]
Việc thực thi của
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
76 được nối lại. Nó có kết quả của cuộc gọi phụ function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
83, vì vậy nó cũng có thể kết thúc việc đánh giá của function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
9, trả về function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
01Sau đó, bối cảnh trước đó được khôi phục
- Bối cảnh. { x. 2, n. 3, ở dòng 5 } pow[2, 3]
Khi nó kết thúc, chúng ta có kết quả là
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
02Độ sâu đệ quy trong trường hợp này là. 3
Như chúng ta có thể thấy từ các hình minh họa ở trên, độ sâu đệ quy bằng với số lượng ngữ cảnh tối đa trong ngăn xếp
Lưu ý các yêu cầu bộ nhớ. Bối cảnh chiếm bộ nhớ. Trong trường hợp của chúng tôi, việc tăng lên lũy thừa của
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
0 thực sự yêu cầu bộ nhớ cho ngữ cảnh function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
0, cho tất cả các giá trị thấp hơn của function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
0Thuật toán dựa trên vòng lặp tiết kiệm bộ nhớ hơn
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
0Lặp đi lặp lại
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
02 sử dụng một ngữ cảnh duy nhất thay đổi function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
07 và function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
08 trong quy trình. Yêu cầu bộ nhớ của nó nhỏ, cố định và không phụ thuộc vào function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
0Bất kỳ đệ quy nào cũng có thể được viết lại dưới dạng vòng lặp. Biến thể vòng lặp thường có thể được thực hiện hiệu quả hơn
…Nhưng đôi khi việc viết lại không hề nhỏ, đặc biệt là khi một hàm sử dụng các cuộc gọi con đệ quy khác nhau tùy thuộc vào điều kiện và hợp nhất các kết quả của chúng hoặc khi việc phân nhánh phức tạp hơn. Và việc tối ưu hóa có thể không cần thiết và hoàn toàn không xứng đáng với những nỗ lực
Đệ quy có thể cho đoạn mã ngắn hơn, dễ hiểu và dễ hỗ trợ hơn. Tối ưu hóa không bắt buộc ở mọi nơi, chủ yếu là chúng tôi cần một mã tốt, đó là lý do tại sao nó được sử dụng
duyệt đệ quy
Một ứng dụng tuyệt vời khác của đệ quy là truyền tải đệ quy
Hãy tưởng tượng, chúng ta có một công ty. Cấu trúc nhân viên có thể được trình bày như một đối tượng
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
0Nói cách khác, một công ty có các bộ phận
Một bộ phận có thể có một loạt các nhân viên. Chẳng hạn, bộ phận
00 có 2 nhân viên. John và Alicefunction pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
Hoặc một bộ phận có thể chia thành các bộ phận nhỏ, như
01 có hai chi nhánh.function pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
02 vàfunction pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
03. Mỗi người trong số họ có nhân viên riêng của họfunction pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
Cũng có thể khi một bộ phận phụ phát triển, nó sẽ chia thành các bộ phận phụ [hoặc nhóm] phụ
Chẳng hạn, bộ phận
02 trong tương lai có thể được chia thành các nhóm chofunction pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
05 vàfunction pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
06. Và họ, có khả năng, có thể chia nhiều hơn nữa. Đó không phải là hình ảnh, chỉ là một cái gì đó để có trong tâm trífunction pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
Bây giờ, giả sử chúng ta muốn một hàm lấy tổng của tất cả các mức lương. Làm thế nào chúng ta có thể làm điều đó?
Một cách tiếp cận lặp đi lặp lại là không dễ dàng, bởi vì cấu trúc không đơn giản. Ý tưởng đầu tiên có thể là tạo một vòng lặp
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
3 trên function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
08 với vòng lặp con lồng nhau trên các bộ phận cấp 1. Nhưng sau đó, chúng ta cần nhiều vòng lặp con lồng nhau hơn để lặp lại nhân viên ở các bộ phận cấp 2 như function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
02… Và sau đó, một vòng lặp con khác bên trong các vòng lặp dành cho các bộ phận cấp 3 có thể xuất hiện trong tương lai? Hãy thử đệ quy
Như chúng ta có thể thấy, khi hàm của chúng ta tính tổng một bộ phận, có hai trường hợp có thể xảy ra
- Hoặc đó là một bộ phận “đơn giản” với một loạt người – sau đó chúng ta có thể tính tổng tiền lương trong một vòng lặp đơn giản
- Hoặc đó là một đối tượng có các phân khu
10 – sau đó chúng ta có thể thực hiện các cuộc gọi đệ quyfunction pow[x, n] { if [n == 1] { return x; } else { return x * pow[x, n - 1]; } } alert[ pow[2, 3] ]; // 8
10 để lấy tổng cho từng phân khu và kết hợp các kết quảfunction pow[x, n] { if [n == 1] { return x; } else { return x * pow[x, n - 1]; } } alert[ pow[2, 3] ]; // 8
Trường hợp đầu tiên là cơ sở của đệ quy, trường hợp tầm thường, khi chúng ta nhận được một mảng
Trường hợp thứ 2 khi chúng ta lấy một đối tượng là bước đệ quy. Một nhiệm vụ phức tạp được chia thành các nhiệm vụ con cho các bộ phận nhỏ hơn. Họ có thể lần lượt chia tách một lần nữa, nhưng sớm hay muộn sự chia tách sẽ kết thúc ở [1]
Thuật toán có lẽ còn dễ đọc hơn từ mã
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
1Mã ngắn và dễ hiểu [hy vọng?]. Đó là sức mạnh của đệ quy. Nó cũng hoạt động đối với bất kỳ cấp độ nào của việc lồng nhau
Đây là sơ đồ của các cuộc gọi
Chúng ta có thể dễ dàng nhận thấy nguyên tắc. đối với một đối tượng
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
12 các cuộc gọi con được thực hiện, trong khi mảng function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
13 là “các lá” của cây đệ quy, chúng cho kết quả ngay lập tứcLưu ý rằng mã sử dụng các tính năng thông minh mà chúng tôi đã đề cập trước đây
- Phương pháp
14 được giải thích trong chương Các phương pháp mảng để lấy tổng của mảngfunction pow[x, n] { if [n == 1] { return x; } else { return x * pow[x, n - 1]; } } alert[ pow[2, 3] ]; // 8
- Vòng lặp
15 để lặp lại các giá trị đối tượng.function pow[x, n] { if [n == 1] { return x; } else { return x * pow[x, n - 1]; } } alert[ pow[2, 3] ]; // 8
16 trả về một mảng của chúngfunction pow[x, n] { if [n == 1] { return x; } else { return x * pow[x, n - 1]; } } alert[ pow[2, 3] ]; // 8
cấu trúc đệ quy
Cấu trúc dữ liệu đệ quy [được xác định đệ quy] là cấu trúc sao chép chính nó thành từng phần
Chúng ta vừa thấy nó trong ví dụ về cấu trúc công ty ở trên
Một bộ phận của công ty là
- Hoặc là một mảng người
- Hoặc một đối tượng với các phòng ban
Đối với các nhà phát triển web, có nhiều ví dụ nổi tiếng hơn. Tài liệu HTML và XML
Trong tài liệu HTML, một thẻ HTML có thể chứa danh sách các
- mẩu văn bản
- bình luận HTML
- Các thẻ HTML khác [có thể chứa các đoạn văn bản/nhận xét hoặc các thẻ khác, v.v.]
Đó là một lần nữa một định nghĩa đệ quy
Để hiểu rõ hơn, chúng ta sẽ đề cập đến một cấu trúc đệ quy khác có tên là “Danh sách được liên kết” có thể là một giải pháp thay thế tốt hơn cho mảng trong một số trường hợp
danh sách liên kết
Hãy tưởng tượng, chúng tôi muốn lưu trữ một danh sách các đối tượng được sắp xếp theo thứ tự
Sự lựa chọn tự nhiên sẽ là một mảng
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
0…Nhưng có một vấn đề với mảng. Thao tác “xóa phần tử” và “chèn phần tử” rất tốn kém. Chẳng hạn, hoạt động của
function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
17 phải đánh số lại tất cả các phần tử để nhường chỗ cho một function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
18 mới và nếu mảng lớn thì sẽ mất thời gian. Tương tự với function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
19Các sửa đổi cấu trúc duy nhất không yêu cầu đánh số lại hàng loạt là những sửa đổi hoạt động với phần cuối của mảng.
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
00. Vì vậy, một mảng có thể khá chậm đối với các hàng đợi lớn, khi chúng ta phải làm việc từ đầuNgoài ra, nếu thực sự cần chèn/xóa nhanh, chúng ta có thể chọn một cấu trúc dữ liệu khác gọi là danh sách liên kết
Phần tử danh sách liên kết được định nghĩa đệ quy là một đối tượng có
01function pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
- Thuộc tính
02 tham chiếu phần tử danh sách được liên kết tiếp theo hoặcfunction pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
03 nếu đó là phần cuốifunction pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
Ví dụ
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
1Biểu diễn đồ họa của danh sách
Một mã thay thế để tạo
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
2Ở đây chúng ta có thể thấy rõ hơn rằng có nhiều đối tượng, mỗi đối tượng có
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
01 và function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
02 trỏ đến hàng xóm. Biến function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
06 là đối tượng đầu tiên trong chuỗi, vì vậy theo các con trỏ function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
02 từ nó, chúng ta có thể tiếp cận bất kỳ phần tử nàoDanh sách có thể dễ dàng chia thành nhiều phần và sau đó nối lại
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
3Tham gia
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
4Và chắc chắn chúng ta có thể chèn hoặc xóa các mục ở bất kỳ đâu
Chẳng hạn, để thêm vào trước một giá trị mới, chúng ta cần cập nhật phần đầu của danh sách
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
5Để xóa một giá trị ở giữa, hãy thay đổi
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
02 của giá trị trước đófunction pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
6Chúng tôi đã làm cho
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
09 nhảy qua function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
05 thành giá trị function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
87. Giá trị function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
05 hiện đã bị loại khỏi chuỗi. Nếu nó không được lưu trữ ở bất kỳ nơi nào khác, nó sẽ tự động bị xóa khỏi bộ nhớKhông giống như mảng, không cần đánh số lại hàng loạt, chúng ta có thể dễ dàng sắp xếp lại các phần tử
Đương nhiên, danh sách không phải lúc nào cũng tốt hơn mảng. Nếu không, mọi người sẽ chỉ sử dụng danh sách
Hạn chế chính là chúng ta không thể dễ dàng truy cập một phần tử theo số của nó. Trong một mảng dễ dàng.
function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
13 là một tài liệu tham khảo trực tiếp. Nhưng trong danh sách, chúng ta cần bắt đầu từ mục đầu tiên và đi function pow[x, n] {
let result = 1;
// multiply result by x n times in the loop
for [let i = 0; i < n; i++] {
result *= x;
}
return result;
}
alert[ pow[2, 3] ]; // 8
02 function pow[x, n] {
if [n == 1] {
return x;
} else {
return x * pow[x, n - 1];
}
}
alert[ pow[2, 3] ]; // 8
10 lần để lấy phần tử thứ N…Nhưng không phải lúc nào chúng ta cũng cần những hoạt động như vậy. Chẳng hạn, khi chúng ta cần một hàng đợi hoặc thậm chí là một deque – cấu trúc được sắp xếp phải cho phép thêm/xóa các phần tử ở cả hai đầu rất nhanh, nhưng không cần truy cập vào phần giữa của nó
Danh sách có thể được nâng cao
- Chúng ta có thể thêm thuộc tính
16 ngoàifunction pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
02 để tham chiếu phần tử trước đó, để di chuyển trở lại dễ dàngfunction pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
- Chúng ta cũng có thể thêm một biến tên là
18 tham chiếu đến phần tử cuối cùng của danh sách [và cập nhật nó khi thêm/xóa các phần tử ở cuối danh sách]function pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
- …Cấu trúc dữ liệu có thể thay đổi tùy theo nhu cầu của chúng tôi
Bản tóm tắt
Điều kiện
Đệ quy là một thuật ngữ lập trình có nghĩa là gọi một hàm từ chính nó. Các hàm đệ quy có thể được sử dụng để giải quyết các tác vụ theo những cách tao nhã
Khi một hàm gọi chính nó, đó được gọi là bước đệ quy. Cơ sở của đệ quy là các đối số hàm làm cho tác vụ trở nên đơn giản đến mức hàm không thực hiện thêm lệnh gọi nào nữa
Cấu trúc dữ liệu được xác định đệ quy là cấu trúc dữ liệu có thể được xác định bằng chính nó
Chẳng hạn, danh sách được liên kết có thể được định nghĩa là cấu trúc dữ liệu bao gồm một đối tượng tham chiếu đến một danh sách [hoặc null]
7function pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
Các cây như cây phần tử HTML hoặc cây bộ phận trong chương này cũng có tính đệ quy tự nhiên. chúng có các nhánh và mỗi nhánh có thể có các nhánh khác
Các hàm đệ quy có thể được sử dụng để duyệt chúng như chúng ta đã thấy trong ví dụ về
19function pow[x, n] { let result = 1; // multiply result by x n times in the loop for [let i = 0; i < n; i++] { result *= x; } return result; } alert[ pow[2, 3] ]; // 8
Bất kỳ hàm đệ quy nào cũng có thể được viết lại thành một hàm lặp. Và điều đó đôi khi được yêu cầu để tối ưu hóa nội dung. Nhưng đối với nhiều tác vụ, một giải pháp đệ quy đủ nhanh và dễ dàng hơn để viết và hỗ trợ