Hàm đệ quy trong Python – cách gọi hàm đệ quy trong python

Hướng dẫn về hàm đệ quy trong Python. Ở đây chúng ta thảo luận về Hàm đệ quy là gì, Thuật toán cho giai thừa trong hàm đệ quy trong Python.

Bạn đang xem : cách gọi hàm đệ quy trong python

Đệ quy-Hàm-in -Python

Hàm đệ quy là gì?

Hàm đệ quy trong Python được sử dụng để gọ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 và chinh phục. 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 chắc chắn. Để khắc phục sự cố này, một vòng lặp có điều kiện tăng dần có thể được sử dụng 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 nhỏ 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ố .

Khởi động Phần mềm Miễn phí của bạn Khóa học phát triển

Phát triển web, ngôn ngữ lập trình, Kiểm tra phần mềm & amp; những người khác

Giả sử chúng ta cần tìm giai thừa của số 5 = & gt; 5! (Vấn đề của chúng tôi)

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

Vì vậy, để nhận được 5! Chúng 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ức là nhận được giai thừa là 1, chúng ta có thể trả về kết quả là

Hãy lấy một ví dụ về mã giả: –

Thuật toán giai thừa

Hãy để chúng tôi xem thuật toán cho giai thừa:

  function get_factorial (n):
    nếu n & lt; 2:
        trả lại 1
    khác:
      trả về get_factorial (n -1)  

Lệnh 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) = trả về 120 # lần gọi đầu tiên
  get_factorial (4) 4 * get_factorial (3) = trả về cuộc gọi thứ 24 #
    get_factorial (3) 3 * get_factorial (2) = trả về 6 # lệnh gọi thứ 3
      get_factorial (2) 2 * get_factorial (1) = trả về 2 # cuộc gọi thứ 4
        get_factorial (1) trả về 1 cuộc gọi thứ 5  

Kết quả cuối cùng sẽ là 120, nơi chúng tôi bắt đầu thực hiện hàm. Hàm đệ quy của chúng ta 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 nơi nó sẽ được thêm vào ngăn xếp và cuộc gọi khác sẽ được thực hiện sau khi giảm số xuống 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ơ bản.
  • Điều kiện cơ bản ở đây là khi số là 1.
  • Mỗi hàm đệ quy đều có điều kiện đệ quy và điều kiện cơ sở của riêng nó.
Xem Thêm  Kiểu CSS cho Bảng - css cho đường viền bảng

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

  • Việc thực hiện đệ quy để nó không thực hiện bất kỳ phép tính nào cho đến khi nó đạt đến điều kiện cơ bản.
  • 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 đệ quy để 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 lặp; nó không mở rộng quy mô như một phương pháp lặp lại.
  • Các ngôn ngữ khác nhau có các cách tối ưu hóa đệ quy khác nhau.
  • Trong nhiều ngôn ngữ, phương thức lặp sẽ hoạt động tốt hơn phương thức đệ 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 các vấn đề phức tạp với đệ quy, trong khi việc lặp lại khá đơn giản.

Một số ưu điểm

  • Trong một số trường hợp, sử dụng đệ quy là cách 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 so với Lặp lại

Chúng tôi đã hiểu đệ quy là gì và nó hoạt động như thế nào trong Python, vì chúng tôi biết tất cả các ngôn ngữ đều có cá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 tôi sẽ so sánh cả hai phương thức đệ quy và lặp lại để xem cách Python hoạt động trong cả hai trường hợp.

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

  def get_recursive_factorial (n):
    nếu n & lt; 0:
        trả về -1
    elif n & lt; 2: # điều kiện cơ sở
        trả lại 1
    khác:
        return n * get_recursive_factorial (n -1) #recursion condition  

2. Vấn đề giai thừa sử dụng phép lặp (lặp)

  def get_iterative_factorial (n):
    nếu n & lt; 0:
        trả về -1
    khác:
        sự thật = 1
        cho tôi trong phạm vi (1, n + 1):
            thực tế * = tôi
        trả về sự thật  

3. Kết quả in

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

Đầu ra:

Bài toán giai thừa sử dụng phép lặp (đầ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 tôi không thể thấy bất kỳ sự khác biệt nào trong quá trình 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à lặp lại trong Python.

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

Xem Thêm  Full Stack là gì? Làm thế nào để trở thành một nhà phát triển ngăn xếp đầy đủ - nhà phát triển ngăn xếp đầy đủ là gì

4. Mã có tính toán thời gian

  thời gian nhập
def get_recursive_factorial (n):
    nếu n & lt; 0:
        trả về -1
    elif n & lt; 2:
        trả lại 1
    khác:
        trả về n * get_recursive_factorial (n-1)
def get_iterative_factorial (n):
    nếu n & lt; 0:
        trả về -1
    khác:
        sự thật = 1
        cho tôi trong phạm vi (1, n + 1):
            thực tế * = tôi
        trả lại sự thật
start_time = time.time ()
get_recursive_factorial (100)
print ("Đệ quy ---% s giây ---"% (time.time () - start_time))
start_time = time.time ()
get_iterative_factorial (100)
print ("Lặp lại ---% s giây ---"% (time.time () - start_time))  

Chúng tôi sẽ thực hiện lặp đi lặp lại 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ể khác nhau tùy theo máy. 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 thi

Trường hợp 1: – Giai thừa của 6:

function

Trường hợp 2: Giai thừa của 50:

interation

Trường hợp 3: Giai thừa của 100:

Đệ quy

Trường hợp 4: Giai thừa của 500:

Hàm đệ quy trong Python

Trường hợp 5: Giai thừa của 1000:

Hàm đệ quy trong Python Chúng tôi đã phân tích cả hai phương pháp trong một vấn đề khác. Hơn nữa, cả hai đều đã hoạt động tương tự, ngoại trừ trường hợp 4.

Chúng tôi đã phân tích cả hai phương pháp trong một vấn đề khác. Hơn nữa, cả hai đều hoạt động tương tự, ngoại trừ trường hợp 4.

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

traceback

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

Python có các 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 tràn ngăn xếp.

Hàm “sys.getrecursionlimit ()” sẽ cho bạn biết giới hạn cho phép đệ quy.

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

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à một 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 lặp lại.
  • Chúng tôi nên sử dụng tính năng lặp lại trong thuật toán của mình vì thuật toán này được tối ưu hóa hơn trong Python và mang lại cho bạn tốc độ tốt hơn.

Các bài báo đượ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ì, một 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–

0

Chia sẻ

Chia sẻ

Xem Thêm  Cách căn giữa văn bản trong CSS - văn bản trung tâm theo chiều ngang css


Xem thêm những thông tin liên quan đến chủ đề cách gọi hàm đệ quy trong python

Bai 23: Hàm đệ quy python giải thích+bài tập – Tự học lập trình python

alt

  • Tác giả: Gà Lại Lập Trình
  • Ngày đăng: 2021-11-16
  • Đánh giá: 4 ⭐ ( 9343 lượt đánh giá )
  • Khớp với kết quả tìm kiếm: ✅ Nếu thấy video hay và bổ ích hãy like và chia sẻ để mình biết
    Các bạn đang quan tâm nhiều đến chủ đề nào và phát triển tiếp cho nội dung đăng sau này
    ✅ Đăng ký kênh để không bỏ lỡ video: http://dangky.tuhoc.cc
    Playlist Video :
    ✅C cơ bản cho người mới: http://csharp.tuhoc.cc/
    ✅ Python căn bản cho người mới: http://python.tuhoc.cc/
    ✅ pygame lập trình game cho người mới : http://pygame.tuhoc.cc/
    ✅ opencv python : http://opencv.tuhoc.cc/
    ✅ clip động lực để học tập : http://dongluc.tuhoc.cc/
    Nhóm thảo luận:
    ✅ Facebook : http://fb.tuhoc.cc/
    ✅ Toàn bộ tài liệu silde bài giảng post tại disord : http://dc.tuhoc.cc/

    python laptrinhpython pythoncoban galailaptrinh pythonvietnam python_cho_nguoi_moi opencv_python tuhoc.cc

Đừng sử dụng đệ qui trong Python

  • Tác giả: nkthanh.dev
  • Đánh giá: 4 ⭐ ( 6535 lượt đánh giá )
  • Khớp với kết quả tìm kiếm: Tôi là một lập trình viên, người mà trước đây rất thích sử dụng các hàm đệ qui, đơn giản bởi vì nó rất ngầu và có thể được sử dụng để khoe khoang kĩ năng lập trình và sự thông minh của tôi. Tuy nhiên, trong đa số các trường hợp, các hàm đệ qui có độ phức tạp rất cao và chúng ta nên tránh sử dụng nó.

Đệ Quy trong Python

  • Tác giả: itzone.com.vn
  • Đánh giá: 3 ⭐ ( 9445 lượt đánh giá )
  • Khớp với kết quả tìm kiếm: The ITZone platform Vietnam is the community for anyone interested in news, training seminars, presentations etc in the IT industry

Hàm trong python

  • Tác giả: nguyenvanhieu.vn
  • Đánh giá: 4 ⭐ ( 1514 lượt đánh giá )
  • Khớp với kết quả tìm kiếm: Trong bài viết này,Lập trình không khó sẽ cùng các bạn tìm hiểu về hàm trong python; Hàm là gì, cú pháp, thành phần và loại của hàm. Ngoài ra, bạn sẽ học cách

Đảo ngược chuỗi trong Python

  • Tác giả: hocdevops.com
  • Đánh giá: 4 ⭐ ( 7418 lượt đánh giá )
  • Khớp với kết quả tìm kiếm:

Function (hàm) trong Python

  • Tác giả: tuhocict.com
  • Đánh giá: 4 ⭐ ( 6672 lượt đánh giá )
  • Khớp với kết quả tìm kiếm: Trong bài học này sẽ chúng ta sẽ xem xét chi tiết các vấn đề liên quan đến việc xây dựng và sử dụng hàm tự tạo trong Python.

Hàm đệ quy trong Python

  • Tác giả: quantrimang.com
  • Đánh giá: 5 ⭐ ( 1076 lượt đánh giá )
  • Khớp với kết quả tìm kiếm: Trong các bài trước, bạn đã biết về hàm Python, các hàm Python tích hợp sẵn và hàm Python do người dùng định nghĩa. Trong bài này chúng ta sẽ tìm hiểu thêm về hàm đệ quy trong Python, hàm tự gọi chính nó, cũng như cách tạo hàm đệ quy và ví dụ minh họa.

Xem thêm các bài viết khác thuộc chuyên mục: Kiến thức lập trình