Hướng dẫn Python – Hàm đệ quy

Trong phần này, bạn sẽ học hàm đệ quy Python.

Hàm đệ quy Python là gì

Một hàm đệ quy là một hàm gọi chính nó và quá trình này được gọi là đệ quy hàm.

Ví dụ: hãy tính giai thừa của một số, chẳng hạn 6 .

6 * 5 * 4 * 3 * 2 * 1

Trong đoạn mã sau, một hàm đệ quy được tạo để tìm giai thừa của một số:

def fact (n): """Recursive function to find factorial""" if n == 1 : return 1 else : return (n * fact(n - 1 )) a = 6 print ( "Factorial of" , a, "=" , fact(a))

Factorial of 6 = 720

Hàm fact(n) là một hàm đệ quy. Hàm fact gọi chính nó với đối số n-1 cho đến khi số trở thành 1 và đây là cách tính giai thừa, tức là nhân số với giai thừa của một số nhỏ hơn một số.

Trong hàm đệ quy này, có một điều kiện cơ bản là khi số trở thành 1 , 1 được trả về và theo cách này, cuộc gọi đệ quy trở nên hữu hạn.

Khi tạo hàm đệ quy phải có điều kiện cơ sở để kết thúc lệnh gọi đệ quy đó.

Giới hạn đệ quy

Như bạn đã nhận thấy, mỗi khi hàm gọi chính nó, nó cần một số bộ nhớ để lưu trữ một số giá trị trung gian. Do đó, hàm đệ quy tiêu tốn nhiều bộ nhớ hơn so với hàm không đệ quy thông thường. Python đặt giới hạn cuộc gọi đệ quy thành 3000 .

>>> import sys >>> sys . getrecursionlimit() 3000

Nó làm tăng RecursionError nếu đệ quy vượt quá 3000 .

def fact (n): """Recursive function to find factorial""" if n == 1 : return 1 else : return (n * fact(n - 1 ))    
print (fact( 4000 ))

Traceback (most recent call last):
  File "<pyshell#2>", line 1, in <module>
    print(factorial(4000))
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  [Previous line repeated 989 more times]
  File "<pyshell#1>", line 2, in factorial
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison

Giải pháp loại bỏ giới hạn đệ quy

Bạn có thể giải quyết giới hạn đệ quy bằng cách đặt giới hạn đệ quy thành một số lớn hơn số đệ quy được yêu cầu.

import sys
sys.setrecursionlimit(5000)
def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return (n * fact(n - 1))
    
print(fact(4000))

Lợi thế của đệ quy

• Sử dụng các hàm đệ quy, vấn đề có thể được chia thành các vấn đề con có thể được giải quyết dễ dàng.
• Mã trở nên gọn gàng và sạch sẽ.

Nhược điểm của đệ quy

• Đôi khi rất khó để theo dõi logic của hàm đệ quy.
• Để giải từng bài toán con sẽ mất nhiều thời gian nên hàm đệ quy không hiệu quả.

Viết bởi Duy Mạnh. Đã đăng ký bản quyền tác giả tại Creativecommons và DMCA