Phương pháp đệ 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 n số tự nhiên trong python. Chúng tôi sẽ viết đoạn mã sau để có được câu trả lời

def sum(n):
    if n <= 1:   # base case
        return n
    else:        # general or recursive case
        ans = sum(n - 1)
    return n + ans


print(sum(6))
đầu ra
Đang làm việc. Khi chúng ta gọi hàm sum() với bất kỳ số nguyên dương nào, chẳng hạn như 6, nó sẽ gọi chính nó theo cách đệ quy bằng cách giảm số. Như đã chỉ ra trong trường hợp đệ quy, mỗi lệnh gọi hàm sẽ thêm đối số số với giá trị là tổng của số đã giảm như được đưa ra bên dưới
tổng(6)=6+tổng(5)tổng(6) = 6 + tổng(5)tổng(6)=6+tổng(5) =6+5+tổng(4)= 6 + 5 + tổng (4 
=6+5+4+3+tổng(2)= 6 + 5 + 4 + 3 + tổng (2)=6+5+4+3+tổng(2)
=6+5+4+3+2+tổng(1)= 6 + 5 + 4 + 3 + 2 + tổng (1)=6+5+4+3+2+tổng(1)
=6+5+4+3+2+1= 6 + 5 + 4 + 3 + 2 + 1=6+5+4+3+2+1
=21= 21=21
Hãy cùng hiểu điều này rõ hơn thông qua sơ đồ quy trình từng bước bên dưới. Quá trình đệ quy bắt đầu khi hàm sum(6) được gọi và kết thúc khi chúng ta chuyển sang trường hợp cơ sở, i. e. , khi tổng (1) trả về 1. Khi giá trị này được trả về, nó sẽ được thêm vào tất cả các giá trị trong ngăn xếp cuộc gọi như được hiển thị và cuối cùng, giá trị 21 được trả về
Tất cả các hàm đệ quy có hai giai đoạn làm việc riêng biệt - giai đoạn cuộn dây và tháo gỡ. Giai đoạn quanh co bắt đầu với hàm đệ quy được gọi lần đầu tiên và di chuyển về phía trước cho đến lần gọi đệ quy cuối cùng. Trong giai đoạn này, không có câu lệnh trả về nào được thực thi. Giai đoạn quanh co kết thúc khi điều kiện của trường hợp cơ sở trở thành đúng trong một cuộc gọi
Đó là khi giai đoạn thư giãn bắt đầu. Trong giai đoạn này, tất cả các hàm đệ quy trả về theo thứ tự ngược lại cho đến khi phiên bản đầu tiên của hàm trả về

Các loại đệ quy trong Python

Có 2 loại hàm đệ quy chủ yếu

1) Đệ quy trực tiếp -

Trong kiểu đệ quy này, hàm gọi chính nó

a) Đệ quy đuôi - Một lời gọi đệ quy được gọi là đệ quy đuôi nếu đó là câu lệnh cuối cùng được thực thi bên trong hàm

Ví dụ về cuộc gọi đệ quy đuôi

Hàm sau in ra các số tự nhiên từ n theo thứ tự giảm dần. Nó được thực hiện bằng cách duyệt các chữ số từ n đến 1 và trả về mỗi chữ số tại một cuộc gọi. Trong ví dụ này, vị trí của câu lệnh in có ý nghĩa quan trọng nhất. Trường hợp cơ sở sẽ là 0, trong đó không có giá trị nào được trả về cho cuộc gọi

Trong lần gọi hàm đầu tiên, câu lệnh print làm cho 5 được hiển thị trên màn hình và disp(4) được thêm vào đầu ngăn xếp. Trong lần gọi tiếp theo, 4 được in và disp(5) được thêm vào ngăn xếp

Tương tự, 3, 2 và 1 được in trong các lời gọi sau. Trong lần gọi cuối cùng, giá trị của n trở thành 0 và do đó trường hợp cơ sở được thỏa mãn, khiến đệ quy kết thúc

def dispn(n):
    if n == 0:
        return  # Base case
    print(n)
    dispn(n - 1)  # Tail Recursive Call


dispn(5)

đầu ra
Ví dụ về một cuộc gọi không phải là đệ quy đuôi
Hàm sau dùng để in các số tự nhiên đến n theo thứ tự tăng dần. So với ví dụ trước, câu lệnh in xuất hiện sau lệnh gọi đệ quy trong hàm này. Vì vậy, các câu lệnh in chỉ phát huy tác dụng trong giai đoạn thư giãn
Tại các lần gọi hàm liên tiếp, disp(5), disp(4), disp(3), disp(2), disp(1) lần lượt được thêm vào đầu ngăn xếp. Khi gặp disp(0) thì điều kiện kết thúc được thỏa mãn, hàm trả về. 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 disp(1) trả về trước, tiếp theo là phần còn lại
Do đó, câu lệnh in của disp(1) xảy ra trước. Vì vậy, các giá trị được in theo thứ tự tăng dần
def dispn(n):
    if n == 0:
        return  # Base case
    dispn(n - 1)  # Not a Tail Recursive Call
    print(n)


dispn(5)

đầu ra
Trong các hàm không trống, nếu lệnh gọi đệ quy xuất hiện trong câu lệnh trả về và không phải là một phần của biểu thức, thì lệnh gọi đó là đệ quy đuôi
Ví dụ về cuộc gọi đệ quy đuôi
Hàm sau dùng để tính ƯCLN của 2 số đã cho. Như ta đã biết, nếu số 0 bé hơn thì ƯCLN của hai số đó sẽ là số lớn hơn. Đây là trường hợp cơ bản của vấn đề của chúng tôi
Theo Thuật toán phần dư của Euclid, chúng ta biết rằng
GCD(a,b)=GCD(b,a/b)GCD (a,b)= GCD (b, a/b)GCD(a,b)=GCD(b,a/b)
Xét a=49 và b=35, sau đó
GCD(49,35)=GCD(35,14)GCD(49,35) = GCD (35, 14)GCD(49,35)=GCD(35,14)
=GCD(14,7)=GCD(14, 7)=GCD(14,7)
=GCD(7,0)=GCD(7, 0)=GCD(7,0)
=7= 7=7
Mã cho điều này là như được đưa ra dưới đây
def GCD(a, b):
    if b == 0:
        return a  # Base case
    return GCD(b, a % b)  # Tail Recursive Call


print(GCD(49, 35))

đầu ra
Ví dụ về một cuộc gọi không phải là đệ quy đuôi
Hàm sau đây được sử dụng để tính giai thừa của một số đã cho. Mặc dù lệnh gọi dường như là đệ quy đuôi do có tên hàm trong câu lệnh trả về, nhưng không phải vì lệnh gọi là một phần của biểu thức trong trường hợp này. Trong ví dụ này, trường hợp cơ bản là khi số là 0 và giá trị một được trả về
Công thức chung cho giai thừa là-
n. =n∗n−1∗n−2∗…. ∗1n. = n*n-1*n-2* …. * 1n. =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 đó
def fact(n):
    if n == 0:
        return 1  # Base case
    return (n * fact(n - 1))  # Not a tail-recursive call


print(fact(5))

đầu ra
Nếu trong một hàm đệ quy, tất cả các lệnh gọi trong hàm đó đều là đệ quy đuôi, thì nó được gọi là đệ quy đuôi. Trong các hàm đệ quy đuôi, tác vụ cuối cùng được thực hiện bởi hàm là một lệnh gọi đệ quy, vì vậy không có thao tác nào đang chờ xử lý sau khi lệnh gọi đệ quy xảy ra. Xét hàm sau, hàm hiển thị 5 số tự nhiên đầu tiên theo thứ tự ngược lại
def tailr(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 <= 1:   # base case
        return n
    else:        # general or recursive case
        ans = sum(n - 1)
    return n + ans


print(sum(6))
0
đầu ra
3. Để tìm số thứ n trong Dãy Fibonacci
Chuỗi Fibonacci là một chuỗi bắt đầu bằng 0,1 trong đó một số có thể được tính bằng tổng của hai số trước đó. Chuỗi Fibonacci 10 số sẽ như sau. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 Bài toán tìm dãy Fibonacci thứ n có thể được định nghĩa đệ quy như sau
trường hợp cơ sở
Khi n=0, giá trị trả về sẽ là 0
Khi n=1 hoặc n=2, giá trị trả về sẽ là 1
trường hợp đệ quy
Tìm tổng của 2 số trước đó bằng cách gọi đệ quy cho bởi
sợi(n−1)+sợi(n−2)sợi(n-1) + sợi(n-2)sợi(n−1)+sợi(n−2)
Mã số
def sum(n):
    if n <= 1:   # base case
        return n
    else:        # general or recursive case
        ans = sum(n - 1)
    return n + ans


print(sum(6))
1
đầu ra
4. đảo ngược số nguyên
Chúng tôi đọc tất cả các số từ phải sang trái để đảo ngược một số nguyên, i. e. , từ hàng đơn vị và ngược lại
E. g. , Số đảo ngược của 765 là 567
thuật toán
Khởi tạo một biến gọi là res thành 0
Nếu số nguyên đã cho lớn hơn 0 a. Thêm res*10+phần còn lại của số vào res. b. Chia số đó cho 10
Nếu chúng ta phải tìm số ngược của 524, chúng ta có thể tiến hành như
Mã số
def sum(n):
    if n <= 1:   # base case
        return n
    else:        # general or recursive case
        ans = sum(n - 1)
    return n + ans


print(sum(6))
2
đầu ra

Đệ quy trong Python với Chuỗi và Mảng

Một chuỗi trong Python có thể được định nghĩa đệ quy là

1. Một chuỗi rỗng
2. Theo sau một ký tự là một chuỗi nhỏ hơn chuỗi ban đầu 1 ký tự

Tương tự, một mảng trong Python có thể được định nghĩa đệ quy là

1. Một mảng trống
2. Theo sau một phần tử của mảng là một mảng nhỏ hơn mảng ban đầu một phần tử mảng

Đây là những nguyên tắc chính mà chúng ta sẽ xem xét khi giải các bài toán trong đệ quy cho chuỗi và mảng

Đệ quy trong Python cho chuỗi và mảng được sử dụng rộng rãi để sắp xếp, đảo ngược, tính toán số lượng phần tử thỏa mãn một điều kiện nhất định và đánh giá chuỗi

Sau đây là một số ví dụ sẽ giúp bạn hiểu rõ hơn về cách sử dụng đệ quy trong mảng và chuỗi trong Python

1. Tăng hay không

Hãy xem xét bạn được cung cấp một mảng các số nguyên được sắp xếp ngẫu nhiên. Bạn được yêu cầu kiểm tra xem mảng có theo thứ tự tăng dần không, tôi. e. , tăng dần với số nhỏ nhất được đặt trước và các số khác theo sau nó. Để thực hiện một giải pháp cho vấn đề này, đã cho một chuỗi, trước tiên chúng ta phải tính độ dài của mảng đã cho. Như đã thảo luận trong định nghĩa đệ quy của một mảng, chúng tôi xem xét 2 trường hợp

• trường hợp cơ sở -
  a. Mảng có độ dài 0 - Mảng rỗng (Không cần sắp xếp)
  b. Mảng có độ dài 1 - Mảng chỉ có một phần tử (Đã được sắp xếp)

Trong cả hai trường hợp này, chúng ta không cần sắp xếp thêm mảng và do đó trả về giá trị True

• Trường hợp đệ quy - Điều này được kích hoạt khi mảng của chúng ta có nhiều hơn một phần tử. Vì vậy, chúng tôi so sánh các cặp phần tử tại mỗi lần gọi lời gọi đệ quy và gọi đệ quy lời gọi tiếp theo như sau

mảng[0] <= mảng [1] và isAscending(mảng[1. ])

Vì vậy, ở lần gọi đầu tiên, các phần tử ở vị trí 0 và 1 được so sánh và giá trị AND của phần tử này và so sánh các phần tử tiếp theo của mảng được trả về

Vào cuối giai đoạn tháo gỡ, giá trị True chỉ được trả về nếu toàn bộ mảng theo thứ tự tăng dần. Chúng ta hãy xem xét một mảng. 1, 2, 3, 4 5. Các thao tác diễn ra như sau

• 1 < = 2 và isAscending(2,3,4,5)
• Đúng và 2<=3 và isAscending(3,4,5)
• Đúng và Đúng và 3<=4 và isAscending(4,5)
• Đúng và Đúng và Đúng và 4<=5 và Đúng
• ĐÚNG VẬY

Mã số

def sum(n):
    if n <= 1:   # base case
        return n
    else:        # general or recursive case
        ans = sum(n - 1)
    return n + ans


print(sum(6))
3
đầu ra
2. Số nguyên âm
Cho một chuỗi, chúng ta phải tính số nguyên âm có trong đó. Đối với điều này, chúng tôi sẽ sử dụng hai chức năng. isVowel() để kiểm tra xem ký tự đang xem xét có phải là nguyên âm hay không và countVowels(), một hàm đệ quy được sử dụng để đếm số nguyên âm có trong chuỗi. Khi hàm CountVowels được gọi, chúng ta chuyển chuỗi và độ dài của nó
Xem xét định nghĩa đệ quy của một chuỗi, như đã đề cập trước đó, chuỗi nhỏ nhất có thể chứa các nguyên âm sẽ dài một ký tự. Nếu chuỗi dài một ký tự, chúng ta kiểm tra xem đó có phải là nguyên âm hay không bằng cách gọi hàm isVowel()
Trong phép so sánh, ký tự đầu tiên được chuyển thành chữ hoa trước khi so sánh để giảm số lần so sánh giữa các trường hợp khác nhau của cùng một nguyên âm. Đối với một chuỗi có nhiều hơn một ký tự, chúng tôi kiểm tra xem ký tự cuối cùng có phải là nguyên âm hay không và nếu có, hãy thêm 1 vào giá trị được trả về bằng cách chuyển chuỗi sau khi loại bỏ ký tự cuối cùng cho hàm đếmVowels()
Giả sử chúng ta đã được cung cấp chuỗi 'Ăn'. Sau lần gọi đầu tiên, chúng tôi sẽ áp dụng các nguyên âm đếm cho chuỗi 'Ea'. Vì 't' không phải là nguyên âm nên số lượng nguyên âm hiện tại là 0. Sau lần gọi thứ hai, chúng ta sẽ áp dụng countVowels() cho chuỗi 'E'. Vì 'a' là một nguyên âm nên số lượng nguyên âm bây giờ sẽ được tăng lên 1
Sau lần gọi thứ ba, chúng ta gọi hàm isVowel() cho E. Vì 'E' là một nguyên âm nên số lượng nguyên âm bây giờ sẽ được thay đổi thành 2. Giá trị cuối cùng, 2 hiện được trả về
Mã số
def sum(n):
    if n <= 1:   # base case
        return n
    else:        # general or recursive case
        ans = sum(n - 1)
    return n + ans


print(sum(6))
4
đầu ra
3. Xuôi ngược đều giống nhau
Palindrome là một từ hoặc dãy số/ký tự đọc ngược giống như đọc xuôi
Ví dụ về palindromes là 12321 và Malayalam. Như đã thảo luận trong định nghĩa đệ quy của một chuỗi, chúng tôi xem xét 2 trường hợp
Trường hợp cơ sở - Chuỗi độ dài 1 - Chuỗi chỉ có một ký tự. Nó là một bảng màu và do đó, chúng tôi trả về một giá trị True
Trường hợp đệ quy - Điều này được kích hoạt khi chuỗi của chúng tôi có nhiều hơn một ký tự
Vì vậy, chúng ta so sánh các cặp ký tự ở hai cực của chuỗi tại mỗi lần gọi đệ quy và gọi đệ quy lần gọi tiếp theo như sau
str[0] == str[-1]andisPalindrome(arr[1. -1])
Ở đây, str[-1] đại diện cho ký tự cuối cùng trong chuỗi. Vì vậy, ở lần gọi đầu tiên, các ký tự ở vị trí 0 và n-1 (trong đó n= độ dài của chuỗi) được so sánh. Và giá trị AND của cái này và so sánh các ký tự sau của chuỗi được trả về. Vào cuối giai đoạn tháo gỡ, một giá trị True chỉ được trả về nếu tất cả các phép so sánh đều trả về True
Xét chuỗi 'ABA'. Các thao tác diễn ra như sau
A == A và isPalindrome(str[1. -1])
Đúng và Đúng
ĐÚNG VẬY
Mã số
def sum(n):
    if n <= 1:   # base case
        return n
    else:        # general or recursive case
        ans = sum(n - 1)
    return n + ans


print(sum(6))
5
đầu ra
4. đảo ngược chuỗi
Cho trước một chuỗi, chúng ta cần đảo ngược nó, i. e. , in chuỗi từ phải sang trái (từ đầu đến cuối). Ta xét 2 trường hợp để giải bài toán này
trường hợp cơ sở. Nếu chuỗi rỗng, tôi. e. , độ dài của nó bằng 0, chúng ta trả về từ hàm
trường hợp đệ quy. Trường hợp này thực hiện cho đến khi chuỗi có ký tự. Ở đây, chúng ta gán ký tự đầu tiên của chuỗi cho một biến tạm thời và gọi hàm strRev() cho phần còn lại của chuỗi
Khi chuỗi trống, giai đoạn tháo gỡ bắt đầu. Nó bắt đầu bằng việc in ký tự cuối cùng trong chuỗi và di chuyển lùi lại cho đến khi tất cả các ký tự được in trên màn hình. Do đó, đầu ra cuối cùng chứa chuỗi theo thứ tự ngược lại
Giả sử rằng chuỗi cần đảo ngược là 'Xin chào'. Sau đó các giai đoạn quấn và tháo sẽ được thực hiện như sau
Mã số
def sum(n):
    if n <= 1:   # base case
        return n
    else:        # general or recursive case
        ans = sum(n - 1)
    return n + ans


print(sum(6))
6
đầu ra

Đệ quy trong Python với Cấu trúc dữ liệu

Dữ liệu trong Python có thể được lưu trữ và sắp xếp hiệu quả hơn bằng cách sử dụng cấu trúc dữ liệu. Các cấu trúc khác nhau được sử dụng dựa trên mục đích được phục vụ. Các cấu trúc dữ liệu này quyết định các hoạt động có thể diễn ra trên dữ liệu

Chúng ta có thể định nghĩa đệ quy một cấu trúc dữ liệu trong Python theo chính nó. Nó giúp chúng ta tận dụng cấu trúc đệ quy; . Loại đệ quy này được gọi là đệ quy cấu trúc. Hãy xem hai ví dụ để hiểu cách đệ quy trong Python được triển khai cho danh sách và cây được liên kết

1. Chèn một nút ở cuối và duyệt danh sách được liên kết bằng cách sử dụng đệ quy

Trong Python, một chuỗi dữ liệu có thể được kết nối bằng các liên kết (ở dạng con trỏ) để tiết kiệm bộ nhớ. Không giống như mảng, danh sách được liên kết chỉ cấp phát bộ nhớ cho các giá trị được lưu trữ, do đó tránh lãng phí bộ nhớ

Danh sách liên kết trong Python được định nghĩa đệ quy là

1. Danh sách liên kết rỗng
2. Một nút theo sau bởi một danh sách được liên kết nhỏ hơn danh sách được liên kết ban đầu một nút

Để chèn một nút vào cuối danh sách liên kết, chúng ta cần duyệt danh sách liên kết cho đến phần tử cuối cùng, i. e. , liên kết của phần tử, là một giá trị null (None). Ví dụ sau đây cho thấy các hàm đệ quy được sử dụng để chèn và duyệt qua danh sách được liên kết

def sum(n):
    if n <= 1:   # base case
        return n
    else:        # general or recursive case
        ans = sum(n - 1)
    return n + ans


print(sum(6))
7
đầu ra
Trong đoạn mã trên, đầu tiên, một lớp nút được định nghĩa. Nó chứa dữ liệu được giữ bởi một nút và liên kết đến phần tử tiếp theo. Ban đầu, phần tử tiếp theo được coi là Không có
Trong lần phân bổ đầu tiên, một đối tượng của lớp nút được khởi tạo với giá trị cho dữ liệu. Vì nút đầu tiên cũng sẽ là nút cuối cùng của danh sách được liên kết tại thời điểm đó, nên nút tiếp theo giữ giá trị Không có
Chèn một nút mới vào cuối danh sách liên kết
trường hợp cơ sở. Nếu danh sách được liên kết trống hoặc chúng tôi đã đến nút cuối cùng, tôi. e. , nếu giá trị của đối tượng là Không, hãy phân bổ một nút mới bằng cách gọi hàm NewNode()
Trường hợp chung. Nếu danh sách liên kết không trống, nó gọi hàm insertEnd()
Để duyệt danh sách liên kết
trường hợp cơ sở. Nếu danh sách trống, tôi. e. , bạn quay lại chính nếu đối tượng có giá trị Không có
Trường hợp chung. In dữ liệu trong nút hiện tại. Và sau đó gọi hàm traverse() cho liên kết của nút hiện tại
2. Inorder Traversal của cây nhị phân
Cây nhị phân có thể có tối đa 2 con, con bên trái và con bên phải lần lượt được gọi là con trái và con phải
Cây nhị phân trong Python là một tập hợp hữu hạn các nút có thể được định nghĩa đệ quy là
Cây rỗng
Một cây bao gồm một nút phân biệt được gọi là gốc và các nút còn lại được phân chia thành hai tập hợp khác nhau, cả hai đều là cây nhị phân
Không giống như cấu trúc dữ liệu tuyến tính, chúng ta có thể duyệt cây nhị phân theo nhiều cách khác nhau. Inorder Traversal của cây nhị phân trả về nút con bên trái (và toàn bộ cây con của nó), theo sau là nút cha và sau đó là nút con bên phải (và toàn bộ cây con của nó). Chúng tôi thường sử dụng đệ quy để duyệt qua các cây nhị phân khi chúng được triển khai bằng cách sử dụng ngăn xếp
Mã số
def sum(n):
    if n <= 1:   # base case
        return n
    else:        # general or recursive case
        ans = sum(n - 1)
    return n + ans


print(sum(6))
8
đầu ra
Trong đoạn mã trên, một nút lớp được xác định đầu tiên. Nút lớp này đại diện cho một nút và chứa dữ liệu mà nó nắm giữ và liên kết với các nút con bên trái và bên phải nếu có. Hàm đệ quy cho truyền tải được truyền địa chỉ của nút gốc
 

			
Phương pháp đệ quy có nghĩa là gì?
			
Đệ quy là  kỹ thuật tự gọi hàm . Kỹ thuật này cung cấp một cách để chia nhỏ các vấn đề phức tạp thành các vấn đề đơn giản dễ giải quyết hơn. 
		
			
Đệ quy trong Python giải thích bằng một ví dụ là gì?
			
Trong hướng dẫn này, bạn sẽ học cách tạo một hàm đệ quy (một hàm gọi chính nó).  Đệ quy là quá trình xác định một thứ gì đó theo chính nó . Một ví dụ về thế giới vật chất sẽ là đặt hai gương song song đối diện nhau. Bất kỳ đối tượng nào ở giữa chúng sẽ được phản ánh đệ quy. 
		
			
Một ví dụ về một phương pháp đệ quy là gì?
			
Ví dụ kinh điển về lập trình đệ quy liên quan đến  tính giai thừa . Giai thừa của một số được tính khi số đó nhân với tất cả các số bên dưới nó cho đến và bằng 1. Ví dụ: giai thừa(5) giống như 5*4*3*2*1 và ​​giai thừa(3) là 3*2*1.