Ví dụ về hàm đệ quy trong Python là gì?

Phạm vi bài viết

• Trong bài viết này, chúng ta sẽ thảo luận về Đệ quy trong Python và lý do tại sao chúng ta sử dụng nó
• Chúng ta sẽ thảo luận về cách đệ quy hoạt động trong Python
• Chúng tôi sẽ thảo luận về nhiều loại đệ quy
• Chúng tôi cũng sẽ thảo luận về các ví dụ khác nhau bằng cách sử dụng Đệ quy trong Python và sử dụng đệ quy trong nhiều cấu trúc dữ liệu

Giới thiệu

Điều gì sẽ xảy ra nếu chúng ta đặt hai gương song song với nhau?

Hãy tưởng tượng bạn muốn biết tên của một người trong hàng mà bạn đang đứng. Bạn yêu cầu mọi người tìm hiểu về nó

Họ tiếp tục hỏi người tiếp theo cho đến khi họ tìm thấy câu trả lời. Sau khi tìm thấy câu trả lời, họ sẽ gửi lại cho đến khi đến tay bạn

Hai ví dụ trên mô tả một quá trình trong đó một hành động cụ thể được lặp lại cho đến khi một điều kiện được đáp ứng. Các quy trình này rất giống với cái mà chúng ta gọi là đệ quy

Một quá trình trong đó một hàm gọi chính nó được gọi là đệ quy. Quá trình này giúp giảm bớt phương pháp giải quyết vấn đề bằng cách thay thế mã lặp bằng câu lệnh đệ quy

Làm việc với đệ quy trong Python

Hãy tưởng tượng bạn đang ngồi trong một khán phòng và bối rối về hàng ghế bạn đang ngồi. Vì bạn không thể đếm đến băng ghế đầu tiên nên bạn hỏi người ngồi ngay trước mặt bạn rằng họ đang ngồi ở hàng nào. Nếu người đó không biết số ghế của mình, anh ta sẽ hỏi người ngay trước mặt mình

Quá trình hỏi sẽ tiếp tục cho đến khi ai đó biết số ghế của họ. Như sơ đồ trên, khi người ngồi hàng 3 báo mình ngồi hàng 3 thì người ngồi sau sẽ cộng thêm 1 và chuyền số 4 của mình cho người ngồi ngay sau. Số hàng sẽ được tính trong mỗi hàng và sẽ được chuyển cho đến khi đến tay bạn. Khi nó đến tay bạn, hãy thêm 1 để nhận số hàng cuối cùng của bạn

Đó chính xác là cách đệ quy trong Python hoạt động

Sử dụng đệ quy trong Python

Mọi người thường thắc mắc tại sao chúng ta nên sử dụng đệ quy khi tồn tại các vòng lặp. Mọi thứ có thể được mã hóa mà không cần đệ quy

Sự khác biệt giữa phép lặp và đệ quy là không có kết thúc tuần tự cho mã đệ quy. Nó kiểm tra một điều kiện cơ bản và có thể tiếp tục miễn là điều đó được thỏa mãn

Đệ quy trong python được sử dụng khi các vấn đề có thể được chia thành các phần đơn giản hơn để tính toán dễ dàng hơn và mã dễ đọc hơn

Ví dụ: nếu bạn muốn tìm kiếm một học sinh trong trường, sẽ có hai cách để thực hiện. Bạn có thể tập hợp tất cả các sinh viên trong một khán phòng và sau đó tìm kiếm cô ấy từng người một. Một phương pháp đơn giản hơn sẽ chia trường học thành các phần cho đến khi phần nhỏ nhất có thể được thực hiện để tìm học sinh, tôi. e. , sẽ hợp lý hơn nếu bạn tìm kiếm lớp cô ấy học trước tiên, sau đó là lớp học và sau đó bạn sẽ có thể tìm thấy vị trí của cô ấy dễ dàng hơn nhiều

Mặc dù đệ quy được tìm thấy để cho kết quả nhanh hơn trong một số trường hợp khi được tối ưu hóa đúng cách, nhưng nó cũng có thể thêm vào việc sử dụng bộ nhớ

Vì vậy, đệ quy chỉ nên được sử dụng khi cần thiết

Hàm đệ quy trong Python

Trong Python hay bất kỳ ngôn ngữ lập trình nào khác, đệ quy là một quá trình trong đó một hàm gọi chính nó. Các hàm như vậy được gọi là hàm đệ quy

Trong ví dụ về khán phòng ở trên, chúng ta sẽ có một hàm đệ quy được gọi làdivide_and_search[], hàm này lấy nhóm sinh viên. Dựa trên sự hiện diện hay vắng mặt của học sinh trong một phần, hàm đệ quy sẽ chạy lại khi gọi hàm mỗi lần, giảm khoảng cách giữa các học sinh

Điều đó có nghĩa là khi hàm đệ quy được gọi lần đầu tiên nơi tất cả những người tham gia trong khán phòng được đặt, chúng tôi sẽ kiểm tra xem sinh viên có mặt ở một phía cụ thể của khán phòng hay không

Nếu học sinh có mặt ở bên trái, nơi chỉ có học sinh lớp lẻ ngồi, bây giờ chúng ta sẽ chuyển học sinh lớp lẻ cho hàm đệ quy. Ở lần gọi sau, học sinh sẽ được tìm kiếm trong các lớp lẻ để tìm xem cô ấy đang học lớp cụ thể nào

Quá trình này sẽ tiếp tục cho đến khi tìm được học sinh cần thiết

Hàm đệ quy trong Python có hai phần

[a] Base Case - Điều này giúp chúng ta kết thúc hàm đệ quy. Đây là một trường hợp đơn giản có thể được trả lời trực tiếp và không sử dụng đệ quy. Nếu hài lòng, nó trả về câu trả lời tính toán cuối cùng. Nếu điều này bị bỏ qua, chức năng sẽ chạy đến vô cùng

Trình thông dịch Python giới hạn số lần gọi đệ quy cho một hàm là 1000 bằng cách đưa ra lỗi đệ quy

[b] Trường hợp Tổng quát [Đệ quy] - Trường hợp này sử dụng đệ quy và được gọi trừ khi điều kiện cơ sở được thỏa mãn

cú pháp

def rec_func_name[]:
   if[condition]                       # base case
       simple statement without recursion
   else                                # general case
       statement calling rec_func_name[]
Trường hợp cơ sở và giải pháp của nó trước tiên phải được xác định để viết hàm đệ quy. Có thể sử dụng nhiều hơn một trường hợp cơ sở tùy thuộc vào tình huống. Khi một trường hợp cơ sở đã được xác định, trường hợp chung hoặc trường hợp đệ quy phải được xác định để mỗi lệnh gọi đệ quy đưa chúng ta đến gần hơn một bước để đạt được trường hợp cơ sở
Hàm đệ quy sử dụng ngăn xếp cuộc gọi. Mỗi khi hàm đệ quy được gọi, hàm đó sẽ được thêm vào đầu ngăn xếp này. Hãy tưởng tượng mở một củ hành tây và bạn đặt mọi lớp vỏ gần nó. Vì vậy, mỗi lớp, được bóc vỏ, sẽ được đặt ở trên cùng của chồng vỏ này
Bây giờ hãy so sánh điều này với một hàm đệ quy. Lột từng lớp sẽ là một lệnh gọi hàm đệ quy. Khi lớp đầu tiên được bóc, lớp bóc [] đầu tiên sẽ được thêm vào trên cùng của ngăn xếp, sau đó lớp tiếp theo sẽ được thêm vào phía trên nó, v.v., cho đến khi quá trình hoàn tất

  

Ví dụ về hàm đệ quy trong Python

Giả sử bạn muốn tìm tổng của n số tự nhiên. Chúng tôi sẽ viết đoạn mã sau để có được câu trả lời

def sum[n]:
    if n  0:
        print[n, end=" "]
        tailr[n - 1]


p = 5
tailr[p]

đầu ra
b] Đệ quy đầu
Nếu trong một hàm đệ quy, câu lệnh cuối cùng không phải là lời gọi đệ quy, tôi. e. , trong giai đoạn tháo gỡ vẫn có một số bước xảy ra và khi đó nó được gọi là đệ quy đầu
Xét hàm sau, hàm này hiển thị năm số tự nhiên đầu tiên theo thứ tự tăng dần. Tại các lần gọi hàm liên tiếp, tiêu đề [5], tiêu đề [4], tiêu đề [3], tiêu đề [2], tiêu đề [1] tương ứng được thêm vào đầu ngăn xếp. Khi chúng ta gặp headr[0], điều kiện kết thúc được thỏa mãn, trả về hàm
Tại thời điểm này, giai đoạn tháo gỡ bắt đầu. Các cuộc gọi trả về theo thứ tự ngược lại, với tiêu đề [1] trả về trước, tiếp theo là phần còn lại. Do đó, câu lệnh in của headr[1] xảy ra trước. Vì vậy, các giá trị được in theo thứ tự tăng dần
def headr[n]:
    if n > 0:
        headr[n - 1]
        print[n, end=" "]


p = 5
headr[5]

đầu ra
Đệ quy gián tiếp - Trong loại đệ quy này, hàm gọi một hàm khác gọi hàm ban đầu. Ở đây, khi hàm A[] được gọi, đầu tiên nó thực hiện câu lệnh in và sau đó gọi hàm B[] với giá trị tăng dần là n. Câu lệnh in của nó được thực thi bên trong hàm B, sau đó hàm A[] với giá trị n giảm đi 5 được gọi
Quá trình tiếp tục khi điều kiện kết thúc không được thỏa mãn
________số 8_______
đầu ra
Chuỗi các hàm trong đệ quy gián tiếp có thể bao gồm bất kỳ hàm nào. Chúng ta có thể có f1[] gọi f2[] gọi f3[] gọi f4[] gọi f5[] lần lượt gọi f1[]. Việc sử dụng đệ quy gián tiếp làm tăng độ phức tạp của mã và do đó không phổ biến lắm

Đệ quy trong Python với số

Đệ quy trong python thường được sử dụng để tính toán các phép tính trên các số. Một số ví dụ phổ biến nhất là tìm giai thừa của một số, hiển thị hoặc tính tổng của một dãy số, đảo ngược số nguyên và kiểm tra tính chia hết

Hãy xem một số ví dụ để hiểu điều này chi tiết hơn

1. chia hết cho 7

Theo quy tắc chia hết của 7, nếu hiệu giữa hai lần chữ số hàng đơn vị của một số và chữ số còn lại là bội của 7 hoặc 0 thì số đó chia hết cho 7

Giả sử một số có dạng 10a+b trong đó b là chữ số hàng đơn vị và a là số/10

Nếu 10a+b chia hết cho 7 thì 2 [10a+b] chia hết cho 7 thì 20 a + 2b chia hết cho 7 21a - a + 2b chia hết cho 7

Loại bỏ bội của 21, ta có a - 2b chia hết cho 7. Vậy 10a-2b chia hết cho 7 khi và chỉ khi [a-2b] chia hết cho 7

Xét số 798
a=79, b=8 => a-2b=79-16= 63 chia hết cho 7. Vậy 798 cũng chia hết cho 7

Hàm đệ quy của chúng tôi được sử dụng cho vấn đề này sẽ có 2 trường hợp đệ quy và 2 trường hợp cơ sở. Nếu số được cung cấp cho chúng tôi là âm, trước tiên chúng tôi sẽ chuyển đổi nó thành số dương và sau đó gọi hàm đệ quy

Điều này được thực hiện bằng cách phủ định số âm được cung cấp cho chúng tôi. Các giá trị nhỏ nhất thỏa mãn phép chia hết của 7 là 0 và 7. Do đó, điều kiện kết thúc cho hàm của chúng ta sẽ là kiểm tra xem số đó là 0 hay 7. Trường hợp cơ sở trả về True nếu điều kiện kết thúc được thỏa mãn. Bây giờ, nếu cả hai điều kiện này đều không được thỏa mãn và số nhỏ hơn 10, điều đó có nghĩa là số đó không chia hết cho 7

Do đó, trong trường hợp như vậy, hàm trả về Sai. Trong ví dụ đã cho, một số chia hết cho 7, nếu a-2b chia hết cho 7. Ở đây, a = num/10 và b = num - num/10 * 10. Vì vậy, để kiểm tra xem số đó có chia hết cho 7 hay không, chúng ta gọi hàm đệ quy cho a-2b tại mỗi lần gọi, sao cho lời gọi đệ quy được thực hiện cho. num/10 = 2* [num=num/10 *10]

Mã số

def isDivisibleBy7[num]:
    if num < 0:
        return isDivisibleBy7[-num]
    if num == 0 or num == 7:
        return True
    if num < 10:
        return False
    return isDivisibleBy7[num // 10 - 2 * [num - num // 10 * 10]]

print[isDivisibleBy7[63]]
print[isDivisibleBy7[70]]

đầu ra
2. Giai thừa của một số
Giai thừa là tích của tất cả các số nhỏ hơn hoặc bằng số đã cho
Ví dụ: Giai thừa của 5=5∗4∗3∗2∗1=1205 = 5 * 4 * 3 * 2 * 1 = 1205=5∗4∗3∗2∗1=120 Trong ví dụ này, trường hợp cơ sở là . Công thức chung cho giai thừa được đưa ra là
n. =n∗n−1. n. = n * n-1. n. =n∗n−1. =n∗n−1∗n−2∗…. ∗1= n* n-1 * n-2 * …. * 1=n∗n−1∗n−2∗…. ∗1
Do đó, tại mỗi lần gọi đệ quy, n hiện tại sẽ được nhân với giai thừa của số trước đó. Vì vậy, giai thừa của 5 sẽ được tính như sau
sự thật[5]=5∗sự thật[4]sự thật[5] = 5 * sự thật [4]sự thật[5]=5∗sự thật[4]
=5∗4∗thực tế[3]= 5 * 4 * thực tế[3]=5∗4∗thực tế[3]
=5∗4∗3∗thực tế[2]= 5 * 4 * 3 * thực tế[2]=5∗4∗3∗thực tế[2]
=5∗4∗3∗2∗thực tế[1]= 5 * 4 * 3 * 2 * thực tế [1]=5∗4∗3∗2∗thực tế[1]
=5∗4∗3∗2∗1= 5 ​​* 4 * 3 * 2 * 1=5∗4∗3∗2∗1
=120= 120=120
Công việc trên có thể được hiểu rõ hơn bằng sơ đồ bên dưới
Mã số
def sum[n]:
    if n