Chức năng đệ quy trong python có nghĩa là gì?

Hàm đệ quy trong Python được sử dụng để gọi lặp đi lặp lại cùng một hàm cho đến khi vòng lặp đạt đến giá trị mong muốn trong quá trình thực thi chương trình bằng cách sử dụng logic chia để trị. Một trong những nhược điểm rõ ràng của việc sử dụng hàm đệ quy trong chương trình Python là 'nếu việc lặp lại không phải là một luồng được kiểm soát, nó có thể dẫn đến việc tiêu thụ một phần bộ nhớ hệ thống. Để khắc phục sự cố này, có thể sử dụng vòng lặp điều kiện tăng dần thay cho hàm Đệ quy trong ngôn ngữ lập trình python

Hàm đệ quy trong Python

Khái niệm đệ quy vẫn giữ nguyên trong Python. Hàm gọi chính nó để chia vấn đề thành các vấn đề nhỏ hơn. Ví dụ đơn giản nhất mà chúng ta có thể nghĩ về đệ quy là tìm giai thừa của một số

Giả sử chúng ta cần tìm giai thừa của số 5 => 5. (Vấn đề của chúng ta)

Để tìm 5. vấn đề có thể được chia thành những vấn đề nhỏ hơn 5. => 5 x 4

Bắt đầu khóa học phát triển phần mềm miễn phí của bạn

Phát triển web, ngôn ngữ lập trình, kiểm thử phần mềm và những thứ khác

Gói phát triển phần mềm tất cả trong một(hơn 600 khóa học, hơn 50 dự án)

Giá
Xem các khóa học

Hơn 600 khóa học trực tuyến. hơn 50 dự án. Hơn 3000 giờ. Giấy chứng nhận có thể kiểm chứng. Truy cập trọn đời
4. 6 (86.754 xếp hạng)

Vì vậy, để có được 5. Ta cần tìm 4. và nhân nó với 5

Hãy tiếp tục phân chia vấn đề

5. = 4. x 5

4. = 3. x 4

3. = 3 x 2

2. = 2 x 1

1. = 1

Khi nó đạt đến đoạn nhỏ nhất, tôi. e. , lấy giai thừa của 1, chúng ta có thể trả về kết quả là

Hãy lấy một ví dụ mã giả. -

Thuật toán cho giai thừa

Chúng ta hãy xem thuật toán cho giai thừa

function get_factorial( n ):
    if n < 2:
        return 1
    else:
      return get_factorial(n -1)

lời gọi hàm

Giả sử chúng ta đang tìm giai thừa của 5

get_factorial(5)		5 * get_factorial(4)  = returns 120  #1st call
  get_factorial(4)	  4 * get_factorial(3) = returns 24 #2nd call
    get_factorial(3)	    3 * get_factorial(2) = returns 6 #3rd call
      get_factorial(2)     2 * get_factorial(1) = returns 2 #4th call
        get_factorial(1)	  returns 1  #5th call

Kết quả cuối cùng sẽ là 120, nơi chúng tôi bắt đầu thực hiện chức năng. Hàm đệ quy của chúng tôi sẽ dừng khi số lượng giảm đến mức có thể thu được kết quả

• Cuộc gọi đầu tiên nhận giai thừa là 5, sẽ dẫn đến một điều kiện đệ quy trong đó nó sẽ được thêm vào ngăn xếp và một cuộc gọi khác sẽ được thực hiện sau khi giảm số lượng xuống còn 4
• Đệ quy này sẽ tiếp tục gọi và chia vấn đề thành các phần nhỏ hơn cho đến khi nó đạt đến điều kiện cơ sở
• Điều kiện cơ bản ở đây là khi số đó là 1
• Mỗi hàm đệ quy có điều kiện đệ quy riêng và điều kiện cơ sở

Ưu và nhược điểm của Hàm đệ quy trong Python

• Việc thực hiện đệ quy là để nó không thực hiện bất kỳ phép tính nào cho đến khi đạt đến điều kiện cơ sở
• Khi đạt đến các điều kiện cơ bản, bạn có thể hết bộ nhớ
• Có thể có một triệu bước trong một vấn đề lớn hoặc chúng ta có thể nói một triệu lần truy cập để thực hiện chương trình có thể dẫn đến lỗi bộ nhớ hoặc lỗi phân đoạn
• 1000000. = 1000000 * 999999. =?
• Đệ quy khác với phép lặp;
• Các ngôn ngữ khác nhau có các tối ưu hóa khác nhau cho đệ quy
• Trong nhiều ngôn ngữ, phương pháp lặp sẽ hoạt động tốt hơn phương pháp đệ quy
• Mọi ngôn ngữ đều có một số hạn chế về độ sâu của đệ quy mà bạn có thể gặp phải khi giải các bài toán lớn
• Đôi khi thật khó để hiểu những vấn đề phức tạp với đệ quy, trong khi nó khá đơn giản với phép lặp

Một số ưu điểm

• Trong một số trường hợp, đệ quy là cách sử dụng thuận tiện và nhanh hơn
• Rất hữu ích trong việc duyệt cây và tìm kiếm nhị phân

Mã Python – Đệ quy vs Lặp lại

Chúng tôi đã hiểu đệ quy là gì và cách nó hoạt động trong Python, vì chúng tôi biết rằng tất cả các ngôn ngữ đều có cách triển khai đệ quy khác nhau để tối ưu hóa bộ nhớ và tính toán. Có thể có trường hợp lặp lại sẽ nhanh hơn đệ quy

Ở đây chúng ta sẽ so sánh cả hai phương thức đệ quy và lặp để xem Python hoạt động như thế nào trong cả hai trường hợp

1. Mã đệ quy cho giai thừa

def get_recursive_factorial(n):
    if n < 0:
        return -1
    elif n < 2:                                     #base condition
        return 1
    else:
        return n * get_recursive_factorial(n -1)    #recursion condition

2. Bài toán giai thừa sử dụng phép lặp (looping)

def get_iterative_factorial(n):
    if n < 0:
        return -1
    else:
        fact = 1
        for i in range( 1, n+1 ):
            fact *= i
        return fact

3. Kết quả in

print(get_recursive_factorial(6))
print(get_iterative_factorial(6))

đầu ra

Như chúng ta có thể thấy, cả hai đều cho cùng một đầu ra vì chúng ta đã viết cùng một logic. Ở đây chúng ta không thể thấy bất kỳ sự khác biệt nào trong việc thực thi

Hãy thêm một số mã thời gian để có thêm thông tin về việc thực thi đệ quy và phép lặp trong Python

Chúng tôi sẽ nhập thư viện "thời gian" và kiểm tra thời gian đệ quy và lặp lại để trả về kết quả

4. Mã với tính toán thời gian

import time
def get_recursive_factorial(n):
    if n < 0:
        return -1
    elif n < 2:
        return 1
    else:
        return n * get_recursive_factorial(n-1)
def get_iterative_factorial(n):
    if n < 0 :
        return -1
    else:
        fact = 1
        for i in range(1, n+1): 
            fact *= i
        return fact
start_time = time.time()
get_recursive_factorial(100)
print("Recursion--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
get_iterative_factorial(100)
print("Iteration--- %s seconds ---" % (time.time() - start_time))

Chúng tôi sẽ thực hiện lặp lại các lần thực hiện với một giá trị khác cho giai thừa và xem kết quả. Các kết quả dưới đây có thể thay đổi từ máy này sang máy khác. Chúng tôi đã sử dụng MacBook Pro 16 GB RAM i7

Chúng tôi đang sử dụng Python 3. 7 để thực hiện

Trường hợp 1. - Giai thừa của 6

trường hợp 2. Thừa số của 50

trường hợp 3. Thừa số của 100

Trường hợp 4. Thừa số của 500

Trường hợp 5. Thừa số 1000

Trong trường hợp 5, chúng tôi đã gặp lỗi khi thực hiện với đệ quy

Python có một hạn chế về độ sâu tối đa mà bạn có thể thực hiện với đệ quy, nhưng vấn đề tương tự tôi có thể giải quyết bằng phép lặp

Python có những hạn chế đối với vấn đề tràn. Python không được tối ưu hóa cho đệ quy đuôi và đệ quy không được kiểm soát gây ra lỗi tràn ngăn xếp

“hệ thống. hàm getrecursionlimit()” sẽ cho bạn biết giới hạn của đệ quy

Giới hạn đệ quy có thể được thay đổi nhưng không được khuyến nghị;

Kết luận – Hàm đệ quy Python

• Đệ quy là một giải pháp hữu ích cho một số vấn đề như duyệt cây và các vấn đề khác
• Python không phải là ngôn ngữ lập trình chức năng và chúng ta có thể thấy ngăn xếp đệ quy không được tối ưu hóa so với phép lặp
• Chúng ta nên sử dụng phép lặp trong thuật toán của mình vì nó được tối ưu hóa hơn trong Python và mang lại cho bạn tốc độ tốt hơn

Bài viết được đề xuất

Đây là hướng dẫn về Hàm đệ quy trong Python. Ở đây chúng ta thảo luận về Hàm đệ quy là gì, hàm đệ quy trong Python, Thuật toán cho giai thừa, v.v. Bạn cũng có thể xem qua các bài viết được đề xuất khác của chúng tôi để tìm hiểu thêm–

Hàm đệ quy trong Python là gì?

Hàm đệ quy nghĩa là gì?

Hàm đệ quy và ví dụ là gì?

Đệ quy trong Python giải thích bằng một ví dụ là gì?