Các loại đệ quy trong python

Question

Một hàm được gọi là đệ quy đuôi, nếu không có thao tác nào đang chờ xử lý khi hàm đệ quy trả về trình gọi của nó

Các hàm như vậy, ngay lập tức trả về giá trị trả về từ hàm gọi
Đây là một phương pháp hiệu quả so với các phương pháp khác, vì không gian ngăn xếp cần thiết ít hơn và thậm chí chi phí tính toán sẽ giảm xuống
Nhớ lại ví dụ đã thảo luận trước đây, giai thừa của một số. Chúng tôi đã viết nó theo cách đệ quy không theo đuôi, vì hoạt động sau cuộc gọi vẫn đang chờ xử lý

#include 

int fact(int n)
{
  if (n == 1)
    return 1;
  else
    return (n * fact(n - 1));
}

int main()
{
  int num = 5;
  std::cout << fact(num) << std::endl;
  return 0;
}

Để làm cho nó đệ quy đuôi, thông tin về các tác vụ đang chờ xử lý phải được theo dõi

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

Nếu bạn quan sát, 'fact2' có cú pháp tương tự như fact ban đầu. Bây giờ, 'thực tế' trong trường hợp đệ quy đuôi không có các phép tính/hoạt động đang chờ xử lý để thực hiện khi trả về từ các lệnh gọi hàm đệ quy.
Giá trị được tính bởi fact2 được trả về đơn giản. Do đó, lượng không gian cần thiết trên ngăn xếp giảm đáng kể. (chỉ dành cho giá trị của n và kết quả, cần có khoảng trống.

Đệ quy tuyến tính và cây

Tùy thuộc vào cấu trúc mà các lệnh gọi hàm đệ quy nhận hoặc phát triển, nó có thể là tuyến tính hoặc phi tuyến tính.
Đó là đệ quy tuyến tính khi, các hoạt động đang chờ xử lý không liên quan đến một lệnh gọi đệ quy khác đến hàm. Hàm đệ quy giai thừa của chúng tôi là đệ quy tuyến tính vì nó chỉ liên quan đến việc nhân các giá trị được trả về và không có lệnh gọi hàm nào nữa.
Đệ quy cây là khi, các hoạt động đang chờ xử lý liên quan đến một lệnh gọi hàm đệ quy khác.
Ví dụ – Chuỗi Fibonacci, các hoạt động đang chờ xử lý có lệnh gọi đệ quy tới hàm đệ quy fib() để tính toán kết quả.

Khi nào không sử dụng đệ quy?

Về cơ bản, bất kỳ vấn đề nào có thể được giải quyết bằng đệ quy cũng có thể được giải quyết bằng phép lặp. Mặc dù đối với một số ứng dụng nhất định như Tháp Hà Nội, một số vấn đề về trí tuệ nhân tạo, v.v., đệ quy được sử dụng vì nó xác định vấn đề một cách tự nhiên, nhưng vẫn có những thời điểm nhất định không nên sử dụng đệ quy

Hàm lặp sử dụng vòng lặp và hàm đệ quy sẽ tự gọi hàm. Hãy lấy một ví dụ

Lưu ý cách khái niệm đang được định nghĩa, tổ tiên, xuất hiện trong định nghĩa của chính nó. Đây là một định nghĩa đệ quy

Trong lập trình, đệ quy có một ý nghĩa rất chính xác. Nó đề cập đến một kỹ thuật mã hóa trong đó một chức năng gọi chính nó

Loại bỏ các quảng cáo

Tại sao sử dụng đệ quy?

Hầu hết các vấn đề lập trình đều có thể giải được mà không cần đệ quy. Vì vậy, nói đúng ra, đệ quy thường không cần thiết

Tuy nhiên, một số tình huống đặc biệt phù hợp với định nghĩa tự quy chiếu—ví dụ: định nghĩa về tổ tiên được trình bày ở trên. Nếu bạn đang nghĩ ra một thuật toán để xử lý trường hợp như vậy theo chương trình, thì một giải pháp đệ quy có thể sẽ rõ ràng và ngắn gọn hơn

Truyền tải cấu trúc dữ liệu dạng cây là một ví dụ điển hình khác. Vì đây là các cấu trúc lồng nhau nên chúng dễ dàng phù hợp với định nghĩa đệ quy. Một thuật toán không đệ quy để đi qua một cấu trúc lồng nhau có thể hơi rắc rối, trong khi một giải pháp đệ quy sẽ tương đối thanh lịch. Một ví dụ về điều này xuất hiện sau trong hướng dẫn này

Mặt khác, đệ quy không dành cho mọi tình huống. Dưới đây là một số yếu tố khác để xem xét

Đối với một số vấn đề, một giải pháp đệ quy, mặc dù có thể, sẽ khó xử hơn là thanh lịch
Việc triển khai đệ quy thường tiêu tốn nhiều bộ nhớ hơn so với các triển khai không đệ quy
Trong một số trường hợp, sử dụng đệ quy có thể dẫn đến thời gian thực hiện chậm hơn

Thông thường, khả năng đọc mã sẽ là yếu tố quyết định lớn nhất. Nhưng nó phụ thuộc vào hoàn cảnh. Các ví dụ được trình bày dưới đây sẽ giúp bạn cảm nhận được khi nào bạn nên chọn đệ quy

Đệ quy trong Python

Khi bạn gọi một hàm trong Python, trình thông dịch sẽ tạo một không gian tên cục bộ mới để các tên được xác định trong hàm đó không xung đột với các tên giống hệt nhau được xác định ở nơi khác. Một chức năng có thể gọi một chức năng khác và ngay cả khi cả hai đều xác định các đối tượng có cùng tên, tất cả đều hoạt động tốt vì các đối tượng đó tồn tại trong các không gian tên riêng biệt

Điều này cũng đúng nếu nhiều phiên bản của cùng một chức năng đang chạy đồng thời. Ví dụ, xét định nghĩa sau

def function():
    x = 10
    function()

Khi

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

4 thực thi lần đầu tiên, Python tạo một không gian tên và gán cho

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

5 giá trị

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

6 trong không gian tên đó. Sau đó,

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

4 tự gọi đệ quy. Lần chạy thứ hai của

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

4, trình thông dịch tạo một không gian tên thứ hai và gán cả

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

6 cho

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

5 ở đó. Hai phiên bản của tên

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

5 này khác biệt với nhau và có thể cùng tồn tại mà không xung đột vì chúng nằm trong các không gian tên riêng biệt

Thật không may, việc chạy

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

4 khi nó đứng tạo ra một kết quả kém truyền cảm hứng, như dấu vết sau đây cho thấy

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

2

Như đã viết, về lý thuyết,

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

4 sẽ tiếp tục mãi mãi, tự gọi đi gọi lại mà không có bất kỳ cuộc gọi nào quay trở lại. Trong thực tế, tất nhiên, không có gì là thực sự mãi mãi. Máy tính của bạn chỉ có rất nhiều bộ nhớ và cuối cùng nó sẽ hết

Python không cho phép điều đó xảy ra. Trình thông dịch giới hạn số lần tối đa mà một hàm có thể gọi chính nó theo cách đệ quy và khi đạt đến giới hạn đó, nó sẽ đưa ra một ngoại lệ

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

44, như bạn thấy ở trên

lưu ý kỹ thuật. Bạn có thể tìm hiểu giới hạn đệ quy của Python là gì với một hàm từ mô-đun

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

45 có tên là

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

46

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

7

Bạn cũng có thể thay đổi nó với

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

47

>>>

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

Bạn có thể đặt nó ở mức khá lớn, nhưng bạn không thể đặt nó ở mức vô hạn

Không có nhiều công dụng đối với một chức năng gọi chính nó một cách bừa bãi mà không có kết thúc. Nó gợi nhớ đến các hướng dẫn mà đôi khi bạn tìm thấy trên chai dầu gội đầu. "Lót, rửa sạch, lặp lại. ” Nếu bạn làm theo những hướng dẫn này theo đúng nghĩa đen, bạn sẽ gội đầu mãi mãi

Lỗ hổng hợp lý này rõ ràng đã xảy ra với một số nhà sản xuất dầu gội đầu, bởi vì một số chai dầu gội thay vì ghi “Tạo bọt, xả, lặp lại khi cần thiết. ” Điều đó cung cấp một điều kiện chấm dứt cho các hướng dẫn. Có lẽ, cuối cùng bạn sẽ cảm thấy tóc của mình đủ sạch để cân nhắc việc lặp lại thêm lần nữa là không cần thiết. Gội đầu sau đó có thể dừng lại

Tương tự, một chức năng gọi chính nó một cách đệ quy phải có một kế hoạch để cuối cùng dừng lại. Các hàm đệ quy thường tuân theo mẫu này

Có một hoặc nhiều trường hợp cơ sở có thể giải trực tiếp mà không cần đệ quy thêm
Mỗi cuộc gọi đệ quy di chuyển giải pháp dần dần đến gần trường hợp cơ sở

Bây giờ bạn đã sẵn sàng để xem nó hoạt động như thế nào với một số ví dụ

Loại bỏ các quảng cáo

Bắt đầu. Đếm ngược đến số không

Ví dụ đầu tiên là một hàm có tên là

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

48, lấy một số dương làm đối số và in các số từ đối số đã chỉ định xuống 0

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

4

Lưu ý cách

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

48 phù hợp với mô hình cho thuật toán đệ quy được mô tả ở trên

Trường hợp cơ sở xảy ra khi
```
def function():
    x = 10
    function()
```
30 bằng 0, tại điểm đó đệ quy dừng lại
Trong lời gọi đệ quy, đối số nhỏ hơn một giá trị hiện tại của
```
def function():
    x = 10
    function()
```
30, vì vậy mỗi lần đệ quy sẽ tiến gần hơn đến trường hợp cơ sở

Ghi chú. Để đơn giản,

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

48 không kiểm tra tính hợp lệ của đối số. Nếu

def function():
    x = 10
    function()

30 không phải là số nguyên hoặc âm, bạn sẽ nhận được ngoại lệ

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

44 vì trường hợp cơ sở không bao giờ đạt được

Phiên bản của

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

48 được hiển thị ở trên làm nổi bật rõ ràng trường hợp cơ sở và lệnh gọi đệ quy, nhưng có một cách ngắn gọn hơn để diễn đạt nó

def function():
    x = 10
    function()

3

Đây là một triển khai không đệ quy có thể có để so sánh

>>>

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

0

Đây là trường hợp mà giải pháp không đệ quy ít nhất cũng rõ ràng và trực quan như giải pháp đệ quy, và có lẽ còn hơn thế nữa

Tính giai thừa

Ví dụ tiếp theo liên quan đến khái niệm toán học về giai thừa. Giai thừa của số nguyên dương n, ký hiệu là n. , được định nghĩa như sau

Nói cách khác, n. là tích của tất cả các số nguyên từ 1 đến n, kể cả

Giai thừa tự nó phù hợp với định nghĩa đệ quy đến nỗi các văn bản lập trình hầu như luôn bao gồm nó như một trong những ví dụ đầu tiên. Bạn có thể diễn đạt định nghĩa của n. đệ quy như thế này

Như với ví dụ hiển thị ở trên, có những trường hợp cơ bản có thể giải quyết được mà không cần đệ quy. Các trường hợp phức tạp hơn là rút gọn, nghĩa là chúng rút gọn thành một trong các trường hợp cơ bản

Các trường hợp cơ bản (n = 0 hoặc n = 1) có thể giải được mà không cần đệ quy
Đối với các giá trị của n lớn hơn 1, n. được xác định theo (n - 1). , vì vậy giải pháp đệ quy dần dần tiếp cận trường hợp cơ sở

Ví dụ, tính toán đệ quy của 4. trông như thế này

Phép tính đệ quy của 4

Các tính toán của 4. , 3. , và 2. tạm dừng cho đến khi thuật toán đạt đến trường hợp cơ sở trong đó n = 1. Tại thời điểm đó, 1. có thể tính toán được mà không cần đệ quy thêm và các phép tính trì hoãn chạy đến khi hoàn thành

Loại bỏ các quảng cáo

Xác định hàm giai thừa Python

Đây là một hàm Python đệ quy để tính giai thừa. Lưu ý mức độ ngắn gọn của nó và mức độ phản ánh định nghĩa được hiển thị ở trên

>>>

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

1

Một chút tô điểm cho chức năng này với một số câu lệnh

def function():
    x = 10
    function()

36 giúp hiểu rõ hơn về trình tự gọi và trả về

>>>

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

3

Lưu ý cách tất cả các cuộc gọi đệ quy xếp chồng lên nhau. Hàm được gọi với

def function():
    x = 10
    function()

30 =

def function():
    x = 10
    function()

38,

def function():
    x = 10
    function()

39,

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

00 và

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

01 liên tiếp trước khi bất kỳ lệnh gọi nào trả về. Cuối cùng, khi

def function():
    x = 10
    function()

30 là

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

01, vấn đề có thể được giải quyết mà không cần đệ quy nữa. Sau đó, mỗi lệnh gọi đệ quy được xếp chồng lên nhau sẽ thoát ra ngoài, trả về

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

01,

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

00,

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

06 và cuối cùng là

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

07 từ lệnh gọi ngoài cùng

Đệ quy không cần thiết ở đây. Bạn có thể triển khai lặp đi lặp lại

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

08 bằng cách sử dụng vòng lặp

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

09

>>>

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

7

Bạn cũng có thể triển khai giai thừa bằng cách sử dụng

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

10 của Python, mà bạn có thể nhập từ mô-đun

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

11

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

20

Một lần nữa, điều này cho thấy rằng nếu một vấn đề có thể giải quyết được bằng đệ quy, thì cũng có khả năng sẽ có một số giải pháp không đệ quy khả thi. Thông thường, bạn sẽ chọn dựa trên cái nào dẫn đến mã trực quan và dễ đọc nhất

Một yếu tố khác cần xem xét là tốc độ thực thi. Có thể có sự khác biệt đáng kể về hiệu suất giữa các giải pháp đệ quy và không đệ quy. Trong phần tiếp theo, bạn sẽ khám phá thêm một chút về những khác biệt này

So sánh tốc độ triển khai giai thừa

Để đánh giá thời gian thực hiện, bạn có thể sử dụng một chức năng được gọi từ một mô-đun cũng được gọi là

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

13. Chức năng này hỗ trợ một số định dạng khác nhau, nhưng bạn sẽ sử dụng định dạng sau trong hướng dẫn này

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

21

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

12 đầu tiên thực hiện các lệnh có trong

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

15 được chỉ định. Sau đó, nó thực thi

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

16 số lượng đã cho của

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

17 và báo cáo thời gian thực hiện tích lũy tính bằng giây

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

22

Ở đây, tham số

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

18 gán cho

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

19 giá trị

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

30. Sau đó,

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

12 in

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

19 một trăm lần. Tổng thời gian thực hiện chỉ hơn 3/100 giây

Các ví dụ hiển thị bên dưới sử dụng

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

12 để so sánh việc triển khai đệ quy, lặp lại và

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

10 của giai thừa từ bên trên. Trong mỗi trường hợp,

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

35 chứa một chuỗi thiết lập xác định hàm

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

08 có liên quan.

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

12 sau đó thực thi

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

38 tổng cộng mười triệu lần và báo cáo tổng số lần thực thi

Đầu tiên, đây là phiên bản đệ quy

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

23

Tiếp theo là thực hiện lặp đi lặp lại

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

24

Cuối cùng, đây là phiên bản sử dụng

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

10

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

25

Trong trường hợp này, việc triển khai lặp lại là nhanh nhất, mặc dù giải pháp đệ quy không thua xa. Phương pháp sử dụng

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

10 là chậm nhất. Số dặm của bạn có thể sẽ thay đổi nếu bạn thử các ví dụ này trên máy của chính mình. Bạn chắc chắn sẽ không nhận được cùng thời gian và thậm chí bạn có thể không nhận được cùng thứ hạng

Nó có quan trọng không?

Nếu bạn sẽ gọi một chức năng nhiều lần, bạn có thể cần tính đến tốc độ thực thi khi chọn cách triển khai. Mặt khác, nếu chức năng sẽ chạy tương đối không thường xuyên, thì sự khác biệt về thời gian thực hiện có thể sẽ không đáng kể. Trong trường hợp đó, tốt hơn hết bạn nên chọn cách triển khai có vẻ thể hiện giải pháp cho vấn đề một cách rõ ràng nhất

Đối với giai thừa, thời gian được ghi ở trên cho thấy việc triển khai đệ quy là một lựa chọn hợp lý

Thành thật mà nói, nếu bạn đang viết mã bằng Python, bạn hoàn toàn không cần triển khai hàm giai thừa. Nó đã có sẵn trong mô-đun

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

72 tiêu chuẩn

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

26

Có lẽ bạn sẽ quan tâm để biết điều này hoạt động như thế nào trong bài kiểm tra thời gian

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

27

Ồ.

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

73 hoạt động tốt hơn so với cách triển khai tốt nhất trong số ba cách triển khai khác được hiển thị ở trên với hệ số xấp xỉ 10

lưu ý kỹ thuật. Việc

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

73 nhanh hơn rất nhiều có lẽ không liên quan gì đến việc nó có được triển khai đệ quy hay không. Nhiều khả năng là do hàm được triển khai bằng C chứ không phải Python. Để đọc thêm về Python và C, hãy xem các tài nguyên này

Ràng buộc Python. Gọi C hoặc C++ từ Python
Xây dựng Mô-đun mở rộng Python C
C cho lập trình viên Python
Hướng dẫn của bạn về mã nguồn CPython
Sách nội bộ CPython

Một chức năng được triển khai trong C hầu như sẽ luôn nhanh hơn một chức năng tương ứng được triển khai trong Python thuần túy

Loại bỏ các quảng cáo

Duyệt một danh sách lồng nhau

Ví dụ tiếp theo liên quan đến việc truy cập từng mục trong cấu trúc danh sách lồng nhau. Hãy xem xét Python sau

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

28

Như sơ đồ sau đây cho thấy,

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

75 chứa hai danh sách con. Bản thân danh sách con đầu tiên chứa một danh sách con khác

Giả sử bạn muốn đếm số phần tử lá trong danh sách này—các đối tượng

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

76 cấp thấp nhất—như thể bạn đã làm phẳng danh sách. Các phần tử lá là ________ 477, ________ 478, _______ 479,

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

200,

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

201,

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

202,

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

203,

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

204,

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

205 và

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

206, vì vậy câu trả lời phải là

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

6

Chỉ gọi

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

208 trong danh sách không đưa ra câu trả lời chính xác

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

29

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

208 đếm các đối tượng ở cấp cao nhất của

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

75, đó là ba phần tử lá

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

77,

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

203 và

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

206 và hai danh sách con

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

214 và

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

215

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

70

Những gì bạn cần ở đây là một chức năng duyệt qua toàn bộ cấu trúc danh sách, bao gồm cả danh sách con. Thuật toán diễn ra như thế này

Đi qua danh sách, kiểm tra lần lượt từng mục
Nếu bạn tìm thấy một phần tử lá, sau đó thêm nó vào số lượng tích lũy
Nếu gặp sublist thì làm như sau
- Thả xuống danh sách phụ đó và tương tự đi qua nó
- Sau khi bạn đã sử dụng hết danh sách phụ, hãy quay lại, thêm các phần tử từ danh sách phụ vào tổng số tích lũy và tiếp tục duyệt qua danh sách gốc mà bạn đã dừng lại

Lưu ý bản chất tự giới thiệu của mô tả này. Đi qua danh sách. Nếu bạn gặp một danh sách phụ, thì hãy đi qua danh sách đó một cách tương tự. Tình huống này yêu cầu đệ quy

Duyệt qua danh sách lồng nhau theo cách đệ quy

Đệ quy phù hợp với vấn đề này rất độc đáo. Để giải quyết nó, bạn cần có khả năng xác định xem một mục danh sách nhất định có phải là mục lá hay không. Để làm được điều đó, bạn có thể sử dụng hàm Python tích hợp

Trong trường hợp của danh sách

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

75, nếu một mục là một thể hiện của loại

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

218, thì đó là một danh sách con. Mặt khác, nó là một mục lá

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

71

Bây giờ bạn đã có sẵn các công cụ để triển khai một hàm đếm các phần tử lá trong danh sách, chiếm các danh sách con theo cách đệ quy

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

72

Nếu bạn chạy

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

219 trên một số danh sách, bao gồm danh sách

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

75 được xác định ở trên, bạn sẽ nhận được

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

73

Như với ví dụ giai thừa, việc thêm một số câu lệnh

def function():
    x = 10
    function()

36 giúp chứng minh chuỗi các cuộc gọi đệ quy và giá trị trả về

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

74

Đây là một bản tóm tắt về những gì đang xảy ra trong ví dụ trên

Dòng 9.

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

222 là

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

223, vì vậy

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

219 đã tìm thấy một danh sách phụ

Dòng 11. Hàm tự gọi đệ quy để đếm các mục trong danh sách con, sau đó thêm kết quả vào tổng tích lũy

Dòng 12.

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

222 là

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

226 nên

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

219 gặp phải lá mục

Dòng 14. Hàm tăng tổng tích lũy lên một để tính cho mục lá

Ghi chú. Để đơn giản hóa, việc triển khai này giả định danh sách được chuyển đến

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

219 chỉ chứa các mục lá hoặc danh sách con, không chứa bất kỳ loại đối tượng tổng hợp nào khác như từ điển hoặc

Đầu ra từ

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

219 khi nó được thực thi trên danh sách

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

75 bây giờ trông như thế này

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

75

Mỗi khi lệnh gọi tới

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

219 kết thúc, nó sẽ trả về số phần tử lá mà nó đã đếm trong danh sách được truyền cho nó. Cuộc gọi cấp cao nhất trả về

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

6, vì nó sẽ

Loại bỏ các quảng cáo

Duyệt một danh sách lồng nhau không đệ quy

Giống như các ví dụ khác được hiển thị cho đến nay, việc duyệt qua danh sách này không yêu cầu đệ quy. Bạn cũng có thể hoàn thành nó lặp đi lặp lại. Đây là một khả năng

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

76

Nếu bạn chạy phiên bản không đệ quy này của

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

219 trên cùng một danh sách như được hiển thị trước đó, bạn sẽ nhận được kết quả tương tự

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

73

Chiến lược được sử dụng ở đây sử dụng một ngăn xếp để xử lý các danh sách con lồng nhau. Khi phiên bản này của

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

219 gặp một danh sách phụ, nó sẽ đẩy danh sách đang được xử lý và chỉ mục hiện tại trong danh sách đó lên một ngăn xếp. Khi nó đã đếm danh sách con, hàm sẽ bật danh sách mẹ và chỉ mục khỏi ngăn xếp để nó có thể tiếp tục đếm ở nơi nó dừng lại

Trên thực tế, về cơ bản, điều tương tự cũng xảy ra trong quá trình triển khai đệ quy. Khi bạn gọi một hàm theo cách đệ quy, Python sẽ lưu trạng thái của phiên bản đang thực thi trên một ngăn xếp để cuộc gọi đệ quy có thể chạy. Khi cuộc gọi đệ quy kết thúc, trạng thái được bật ra khỏi ngăn xếp để phiên bản bị gián đoạn có thể tiếp tục. Đó là cùng một khái niệm, nhưng với giải pháp đệ quy, Python đang thực hiện công việc tiết kiệm trạng thái cho bạn

Lưu ý mức độ ngắn gọn và dễ đọc của mã đệ quy khi so sánh với phiên bản không đệ quy

Truyền tải danh sách lồng nhau đệ quy và không đệ quy

Đây là trường hợp sử dụng đệ quy chắc chắn là một lợi thế

Phát hiện Palindromes

Việc lựa chọn có sử dụng đệ quy để giải quyết vấn đề hay không phụ thuộc phần lớn vào bản chất của vấn đề. Ví dụ, thừa số tự nhiên chuyển thành cách thực hiện đệ quy, nhưng giải pháp lặp lại cũng khá đơn giản. Trong trường hợp đó, nó được cho là một sự tung lên

Vấn đề duyệt danh sách là một câu chuyện khác. Trong trường hợp đó, giải pháp đệ quy rất tao nhã, trong khi giải pháp không đệ quy là cồng kềnh nhất

Đối với vấn đề tiếp theo, sử dụng đệ quy được cho là ngớ ngẩn

Palindrome là một từ đọc ngược giống như đọc xuôi. Ví dụ bao gồm các từ sau

Xe đua
Cấp độ
Chèo xuồng
người hồi sinh
công dân

Nếu được yêu cầu nghĩ ra một thuật toán để xác định xem một chuỗi có phải là đối xứng hay không, có lẽ bạn sẽ nghĩ ra thứ gì đó như “Đảo ngược chuỗi và xem nó có giống với chuỗi ban đầu không. ” Bạn không thể nhận được nhiều đơn giản hơn thế

Thậm chí hữu ích hơn, cú pháp cắt lát

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

235 của Python để đảo ngược chuỗi cung cấp một cách thuận tiện để mã hóa nó

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

78

Điều này là rõ ràng và ngắn gọn. Hầu như không cần tìm kiếm giải pháp thay thế. Nhưng để giải trí, hãy xem xét định nghĩa đệ quy này của một bảng màu

trường hợp cơ sở. Một chuỗi rỗng và một chuỗi bao gồm một ký tự đơn lẻ vốn dĩ là palindromic
đệ quy rút gọn. Một chuỗi có độ dài bằng hai hoặc lớn hơn là một đối xứng nếu nó thỏa mãn cả hai tiêu chí này
1. Ký tự đầu và cuối giống nhau
2. Chuỗi con giữa ký tự đầu tiên và ký tự cuối cùng là một bảng màu

Cắt lát cũng là bạn của bạn ở đây. Đối với một chuỗi

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

236, lập chỉ mục và cắt cho các chuỗi con sau

Ký tự đầu tiên là

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

237

Ký tự cuối cùng là

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

238

Chuỗi con giữa ký tự đầu tiên và ký tự cuối cùng là

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

239

Vì vậy, bạn có thể định nghĩa đệ quy

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

240 như thế này

>>>

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

79

Đó là một bài tập thú vị để suy nghĩ theo cách đệ quy, ngay cả khi nó không đặc biệt cần thiết

Loại bỏ các quảng cáo

Sắp xếp với Quicksort

Ví dụ cuối cùng được trình bày, giống như duyệt danh sách lồng nhau, là một ví dụ điển hình về một vấn đề gợi ý một cách tiếp cận đệ quy một cách rất tự nhiên. Đây là một thuật toán sắp xếp hiệu quả được phát triển bởi nhà khoa học máy tính người Anh Tony Hoare vào năm 1959

Quicksort là thuật toán chia để trị. Giả sử bạn có một danh sách các đối tượng để sắp xếp. Bạn bắt đầu bằng cách chọn một mục trong danh sách, được gọi là mục trục. Đây có thể là bất kỳ mục nào trong danh sách. Sau đó, bạn phân vùng danh sách thành hai danh sách con dựa trên mục trục và sắp xếp đệ quy các danh sách con

Các bước của thuật toán như sau

Chọn mục trục
Phân vùng danh sách thành hai danh sách con
1. Những mặt hàng nhỏ hơn mặt hàng trục
2. Những mục lớn hơn mục trục
Sắp xếp nhanh các danh sách con theo cách đệ quy

Mỗi phân vùng tạo ra các danh sách con nhỏ hơn, vì vậy thuật toán được rút gọn. Các trường hợp cơ sở xảy ra khi các danh sách con trống hoặc có một phần tử, vì chúng vốn đã được sắp xếp

Chọn mục Pivot

Thuật toán Quicksort sẽ hoạt động bất kể mục nào trong danh sách là mục trục. Nhưng một số lựa chọn tốt hơn những lựa chọn khác. Hãy nhớ rằng khi phân vùng, hai danh sách con được tạo. một với các mục nhỏ hơn mục trục và một với các mục lớn hơn mục trục. Lý tưởng nhất là hai danh sách con có độ dài gần bằng nhau

Hãy tưởng tượng rằng danh sách ban đầu của bạn để sắp xếp có tám mục. Nếu mỗi phân vùng dẫn đến các danh sách con có độ dài gần bằng nhau, thì bạn có thể tiếp cận các trường hợp cơ bản trong ba bước

Phân vùng tối ưu, danh sách tám mục

Ở đầu kia của quang phổ, nếu lựa chọn mục trục của bạn đặc biệt không may mắn, thì mỗi phân vùng sẽ dẫn đến một danh sách con chứa tất cả các mục ban đầu ngoại trừ mục trục và một danh sách con khác trống. Trong trường hợp đó, phải mất bảy bước để rút gọn danh sách thành các trường hợp cơ bản

Phân vùng dưới mức tối ưu, Danh sách tám mục

Thuật toán Quicksort sẽ hiệu quả hơn trong trường hợp đầu tiên. Nhưng bạn cần biết trước một số điều về bản chất của dữ liệu bạn đang sắp xếp để chọn các mục trục tối ưu một cách có hệ thống. Trong mọi trường hợp, không có sự lựa chọn nào là tốt nhất cho mọi trường hợp. Vì vậy, nếu bạn đang viết một hàm Quicksort để xử lý trường hợp chung, thì việc lựa chọn mục trục có phần tùy ý

Mục đầu tiên trong danh sách là một lựa chọn phổ biến, cũng như mục cuối cùng. Chúng sẽ hoạt động tốt nếu dữ liệu trong danh sách được phân phối khá ngẫu nhiên. Tuy nhiên, nếu dữ liệu đã được sắp xếp hoặc thậm chí gần như vậy, thì những dữ liệu này sẽ dẫn đến phân vùng dưới mức tối ưu như được hiển thị ở trên. Để tránh điều này, một số thuật toán Quicksort chọn mục ở giữa trong danh sách làm mục trục

Một tùy chọn khác là tìm trung vị của các mục đầu tiên, cuối cùng và ở giữa trong danh sách và sử dụng mục đó làm mục xoay vòng. Đây là chiến lược được sử dụng trong mã mẫu bên dưới

Thực hiện phân vùng

Khi bạn đã chọn mục trục, bước tiếp theo là phân vùng danh sách. Một lần nữa, mục tiêu là tạo hai danh sách phụ, một danh sách chứa các mục nhỏ hơn mục trục và danh sách còn lại chứa các mục lớn hơn

Bạn có thể thực hiện điều này trực tiếp tại chỗ. Nói cách khác, bằng cách hoán đổi các mục, bạn có thể xáo trộn các mục trong danh sách xung quanh cho đến khi mục trục nằm ở giữa, tất cả các mục nhỏ hơn ở bên trái và tất cả các mục lớn hơn ở bên phải. Sau đó, khi bạn sắp xếp nhanh các danh sách con theo cách đệ quy, bạn sẽ chuyển các phần của danh sách sang bên trái và bên phải của mục trục

Ngoài ra, bạn có thể sử dụng khả năng thao tác danh sách của Python để tạo danh sách mới thay vì thao tác trên danh sách ban đầu tại chỗ. Đây là cách tiếp cận được thực hiện trong đoạn mã dưới đây. Thuật toán như sau

Chọn mục trục bằng phương pháp trung bình của ba được mô tả ở trên
Sử dụng mục trục, tạo ba danh sách phụ
1. Các mục trong danh sách ban đầu nhỏ hơn mục trục
2. Bản thân mục trục
3. Các mục trong danh sách ban đầu lớn hơn mục trục
Danh sách Quicksort đệ quy 1 và 3
Nối cả ba danh sách lại với nhau

Lưu ý rằng điều này liên quan đến việc tạo danh sách con thứ ba chứa chính mục trục. Một lợi thế của phương pháp này là nó xử lý trơn tru trường hợp mục trục xuất hiện trong danh sách nhiều lần. Trong trường hợp đó, danh sách 2 sẽ có nhiều hơn một phần tử

Loại bỏ các quảng cáo

Sử dụng Triển khai Quicksort

Bây giờ nền tảng đã sẵn sàng, bạn đã sẵn sàng chuyển sang thuật toán Quicksort. Đây là mã Python

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

0

Đây là những gì mỗi phần của

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

241 đang làm

Dòng 4. Các trường hợp cơ bản khi danh sách trống hoặc chỉ có một phần tử
Dòng 7 đến 13. Tính toán mục trục theo phương pháp trung bình của ba
Dòng 14 đến 18. Tạo ba danh sách phân vùng
Dòng 20 đến 24. Sắp xếp đệ quy và sắp xếp lại danh sách phân vùng

Ghi chú. Ví dụ này có ưu điểm là ngắn gọn và tương đối dễ đọc. Tuy nhiên, đó không phải là cách triển khai hiệu quả nhất. Cụ thể, việc tạo danh sách phân vùng trên các dòng 14 đến 18 liên quan đến việc lặp qua danh sách ba lần riêng biệt, điều này không tối ưu từ quan điểm về thời gian thực hiện

Dưới đây là một số ví dụ về

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

241 đang hoạt động

>>>

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

1

Đối với mục đích thử nghiệm, bạn có thể xác định một hàm ngắn để tạo danh sách các số ngẫu nhiên giữa

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

01 và

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

244

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

2

Bây giờ bạn có thể sử dụng

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

245 để kiểm tra

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

241

>>>

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

3

Để hiểu thêm về cách thức hoạt động của

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

241, hãy xem sơ đồ bên dưới. Điều này cho thấy trình tự đệ quy khi sắp xếp danh sách mười hai phần tử

Thuật toán Quicksort, Danh sách 12 phần tử

Trong bước đầu tiên, các giá trị danh sách đầu tiên, giữa và cuối cùng lần lượt là

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

248,

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

249 và

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

250. Giá trị trung bình là

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

248, do đó giá trị đó sẽ trở thành mục xoay vòng. Phân vùng đầu tiên sau đó bao gồm các danh sách con sau

SublistItems

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

252Các mục nhỏ hơn mục trục chính

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

253Bản thân mục trục

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

254Các mục lớn hơn mục trục

Mỗi danh sách con sau đó được phân vùng đệ quy theo cùng một cách cho đến khi tất cả các danh sách con chứa một phần tử hoặc trống. Khi các cuộc gọi đệ quy trở lại, các danh sách được sắp xếp lại theo thứ tự được sắp xếp. Lưu ý rằng trong bước thứ hai đến bước cuối cùng ở bên trái, mục xoay vòng

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

255 xuất hiện trong danh sách hai lần, do đó, danh sách mục xoay vòng có hai phần tử

Phần kết luận

Điều đó kết thúc hành trình của bạn thông qua đệ quy, một kỹ thuật lập trình trong đó một hàm gọi chính nó. Đệ quy không phải lúc nào cũng phù hợp với mọi nhiệm vụ. Nhưng một số vấn đề lập trình gần như kêu cứu. Trong những tình huống đó, đó là một kỹ thuật tuyệt vời để bạn tùy ý sử dụng

Trong hướng dẫn này, bạn đã học

Ý nghĩa của việc một hàm gọi chính nó một cách đệ quy
Cách thiết kế các hàm Python hỗ trợ đệ quy
Những yếu tố cần xem xét khi lựa chọn có hay không giải quyết vấn đề theo cách đệ quy
Cách triển khai hàm đệ quy trong Python

Bạn cũng đã xem một số ví dụ về thuật toán đệ quy và so sánh chúng với các giải pháp không đệ quy tương ứng

Bây giờ bạn sẽ ở một vị trí thuận lợi để nhận ra khi nào đệ quy được yêu cầu và sẵn sàng sử dụng nó một cách tự tin khi cần thiết. Nếu bạn muốn khám phá thêm về đệ quy trong Python, hãy xem Tư duy đệ quy trong Python

Đánh dấu là đã hoàn thành

🐍 Thủ thuật Python 💌

Nhận một Thủ thuật Python ngắn và hấp dẫn được gửi đến hộp thư đến của bạn vài ngày một lần. Không có thư rác bao giờ. Hủy đăng ký bất cứ lúc nào. Được quản lý bởi nhóm Real Python

Gửi cho tôi thủ thuật Python »

Giới thiệu về John Sturtz

John là một Pythonista cuồng nhiệt và là thành viên của nhóm hướng dẫn Real Python

» Thông tin thêm về John

Mỗi hướng dẫn tại Real Python được tạo bởi một nhóm các nhà phát triển để nó đáp ứng các tiêu chuẩn chất lượng cao của chúng tôi. Các thành viên trong nhóm đã làm việc trong hướng dẫn này là

Aldren

Bartosz

Joanna

Gia-cốp

Bậc thầy Kỹ năng Python trong thế giới thực Với quyền truy cập không giới hạn vào Python thực

Tham gia với chúng tôi và có quyền truy cập vào hàng nghìn hướng dẫn, khóa học video thực hành và cộng đồng các Pythonistas chuyên gia

Nâng cao kỹ năng Python của bạn »

Bậc thầy Kỹ năng Python trong thế giới thực
Với quyền truy cập không giới hạn vào Python thực

Tham gia với chúng tôi và có quyền truy cập vào hàng ngàn hướng dẫn, khóa học video thực hành và cộng đồng Pythonistas chuyên gia

Nâng cao kỹ năng Python của bạn »

Bạn nghĩ sao?

Đánh giá bài viết này

Tweet Chia sẻ Chia sẻ Email

Bài học số 1 hoặc điều yêu thích mà bạn đã học được là gì?

Mẹo bình luận. Những nhận xét hữu ích nhất là những nhận xét được viết với mục đích học hỏi hoặc giúp đỡ các sinh viên khác. và nhận câu trả lời cho các câu hỏi phổ biến trong cổng thông tin hỗ trợ của chúng tôi

Đệ quy trực tiếp và gián tiếp trong Python là gì?

Hàm gọi chính nó hoặc hai hàm gọi lẫn nhau. Các hàm gọi chính nó là hàm đệ quy trực tiếp và khi hai hàm gọi lẫn nhau thì các hàm đó được gọi là hàm đệ quy gián tiếp .

Đệ quy trong Python là gì?

Python cũng chấp nhận đệ quy hàm, nghĩa là một hàm đã xác định có thể gọi chính nó . Đệ quy là một khái niệm toán học và lập trình phổ biến. Nó có nghĩa là một chức năng gọi chính nó. Điều này có lợi là bạn có thể lặp qua dữ liệu để đạt được kết quả.

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

Trường hợp đệ quy có ba thành phần. .

chia vấn đề thành một hoặc nhiều phần đơn giản hơn hoặc nhỏ hơn của vấn đề,

gọi hàm (đệ quy) trên từng phần và

kết hợp các giải pháp của các phần thành một giải pháp cho vấn đề

Các loại đệ quy là gì?

Đệ quy chủ yếu có hai loại tùy thuộc vào việc một hàm gọi chính nó từ bên trong chính nó hay nhiều hàm gọi lẫn nhau. Cái đầu tiên được gọi là đệ quy trực tiếp và một cái khác được gọi là đệ quy gián tiếp .

programming python

Các loại đệ quy trong python

Đệ quy tuyến tính và cây

Khi nào không sử dụng đệ quy?

Tại sao sử dụng đệ quy?

Đệ quy trong Python

Bắt đầu. Đếm ngược đến số không

Tính giai thừa

Xác định hàm giai thừa Python

So sánh tốc độ triển khai giai thừa

Duyệt một danh sách lồng nhau

Duyệt qua danh sách lồng nhau theo cách đệ quy

Duyệt một danh sách lồng nhau không đệ quy

Phát hiện Palindromes

Sắp xếp với Quicksort

Chọn mục Pivot

Thực hiện phân vùng

Sử dụng Triển khai Quicksort

Phần kết luận

Đệ quy trực tiếp và gián tiếp trong Python là gì?

Đệ quy trong Python là gì?

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

Các loại đệ quy là gì?

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội