Đối tượng hàm đệ quy JavaScript

Đệ 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ần

pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16

Có hai cách để thực hiện nó

1. suy nghĩ lặp đi lặp lại. 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

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

0

1. Nếu

   function pow(x, n) {
     if (n == 1) {
       return x;
     } else {
       return x * pow(x, n - 1);
     }
   }
   
   alert( pow(2, 3) ); // 8

   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ằ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
2. Nếu không, chúng ta có thể đại diện 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 là

   function pow(x, n) {
     if (n == 1) {
       return x;
     } else {
       return x * pow(x, n - 1);
     }
   }
   
   alert( pow(2, 3) ); // 8

   9. Trong môn toán, người ta sẽ viết

   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. Đâ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ớ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

   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ới

   function pow(x, n) {
     if (n == 1) {
       return x;
     } else {
       return x * pow(x, n - 1);
     }
   }
   
   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 khi

   function pow(x, n) {
     if (n == 1) {
       return x;
     } else {
       return x * pow(x, n - 1);
     }
   }
   
   alert( pow(2, 3) ); // 8

   0 đạt đế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

   05

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

5

Ví 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

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

2. function pow(x, n) {
     if (n == 1) {
       return x;
     } else {
       return x * pow(x, n - 1);
     }
   }
   
   alert( pow(2, 3) ); // 8

   60

3. function pow(x, n) {
     if (n == 1) {
       return x;
     } else {
       return x * pow(x, n - 1);
     }
   }
   
   alert( pow(2, 3) ); // 8

   61

4. function pow(x, n) {
     if (n == 1) {
       return x;
     } else {
       return x * pow(x, n - 1);
     }
   }
   
   alert( pow(2, 3) ); // 8

   62

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ễ đọc

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

alert( pow(2, 3) ); // 8

6

Số 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ác

Mộ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

68

bộ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àm

Chú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

64

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

7

Cá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 _______ 376

bộ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

1. Bối cảnh hiện tại được "ghi nhớ" trên đầu ngăn xếp
2. Bối cảnh mới được tạo cho subcall
3. 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

79

Vì 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

82

Mộ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

83

Lố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 động

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

alert( pow(2, 3) ); // 8

8

Khô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

87

Khi 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

01

Sau đó, 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

0

Thuậ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

0

Lặ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

0

Bấ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

0

Nó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

  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 có 2 nhân viên. John và Alice

• Hoặc một bộ phận có thể chia thành các bộ phận 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

  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ọ

• 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

  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 trong tương lai có thể được chia thành các nhó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

  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í

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

1. 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
2. Hoặc đó là một đối tượng có các phân khu

   function pow(x, n) {
     if (n == 1) {
       return x;
     } else {
       return x * pow(x, n - 1);
     }
   }
   
   alert( pow(2, 3) ); // 8

   10 – sau đó chúng ta có thể thực hiện các cuộc gọi đệ quy

   function 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ả

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

1

Mã 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ức

Lư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

  function pow(x, n) {
    if (n == 1) {
      return x;
    } else {
      return x * pow(x, n - 1);
    }
  }
  
  alert( pow(2, 3) ); // 8

  14 được giải thích trong chương Các phương pháp mảng để lấy tổng của mảng
• 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

  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úng

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

19

Cá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ừ đầu

Ngoà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ó

• 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
• Thuộc tí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 tham chiếu phần tử danh sách được liên kết tiếp theo hoặ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

  03 nếu đó là phần cuối

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

1

Biể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ào

Danh 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

3

Tham 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

4

Và 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

6

Chú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

  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

  16 ngoà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 để tham chiếu phần tử trước đó, để di chuyển trở lại dễ dàng
• Chúng ta cũng có thể thêm một biến tên 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

  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)
• …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)

  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

  7

  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ề

  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

  19

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ợ

Bốn loại đệ quy là gì?

3 phần của hàm đệ quy là gì?

Chức năng đệ quy trong JavaScript với ví dụ là gì?

JavaScript có hỗ trợ chức năng đệ quy không?