Hướng dẫn recursive function examples in python - ví dụ về hàm đệ quy trong python

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 tự gọi].

Đệ quy là gì?

Đệ quy là quá trình xác định một cái gì đó theo chính nó.

Một ví dụ thế giới vật lý sẽ là đặt hai gương song song đối diện nhau. Bất kỳ đối tượng ở giữa chúng sẽ được phản ánh đệ quy.

Chức năng đệ quy Python

Trong Python, chúng ta biết rằng một hàm có thể gọi các chức năng khác. Thậm chí có thể cho chức năng gọi chính nó. Các loại cấu trúc này được gọi là các hàm đệ quy.

Hình ảnh sau đây cho thấy hoạt động của hàm đệ quy gọi là

factorial[3]          # 1st call with 3
3 * factorial[2]      # 2nd call with 2
3 * 2 * factorial[1]  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

Sau đây là một ví dụ về hàm đệ quy để tìm giai thừa của một số nguyên.

Factorial của một số là sản phẩm của tất cả các số nguyên từ 1 đến số đó. Ví dụ: giai thừa của 6 [ký hiệu là 6!] Là 1*2*3*4*5*6 = 720.

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

def factorial[x]:
    """This is a recursive function
    to find the factorial of an integer"""

    if x == 1:
        return 1
    else:
        return [x * factorial[x-1]]


num = 3
print["The factorial of", num, "is", factorial[num]]

Đầu ra

The factorial of 3 is 6

Trong ví dụ trên,

factorial[3]          # 1st call with 3
3 * factorial[2]      # 2nd call with 2
3 * 2 * factorial[1]  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

Khi chúng ta gọi hàm này với số nguyên dương, nó sẽ tự gọi mình bằng cách giảm số.

Mỗi hàm nhân số số với giai thừa của số bên dưới nó cho đến khi nó bằng một. Cuộc gọi đệ quy này có thể được giải thích trong các bước sau.

factorial[3]          # 1st call with 3
3 * factorial[2]      # 2nd call with 2
3 * 2 * factorial[1]  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

Chúng ta hãy xem một hình ảnh hiển thị một quá trình từng bước về những gì đang diễn ra:

Đệ quy của chúng tôi kết thúc khi số lượng giảm xuống 1. cái này được gọi là điều kiện cơ sở.

Mỗi chức năng đệ quy phải có một điều kiện cơ sở dừng đệ quy hoặc nếu không thì hàm tự gọi chính nó.

Thông dịch viên Python giới hạn độ sâu của đệ quy để giúp tránh các đệ quy vô hạn, dẫn đến tràn chồng.

Theo mặc định, độ sâu tối đa của đệ quy là 1000. Nếu giới hạn được vượt qua, nó sẽ dẫn đến

factorial[3]          # 1st call with 3
3 * factorial[2]      # 2nd call with 2
3 * 2 * factorial[1]  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

def recursor[]:
    recursor[]
recursor[]

Đầu ra

Traceback [most recent call last]:
  File "", line 3, in 
  File "", line 2, in a
  File "", line 2, in a
  File "", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Trong ví dụ trên,

factorial[3]          # 1st call with 3
3 * factorial[2]      # 2nd call with 2
3 * 2 * factorial[1]  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

2 là một hàm đệ quy như nó tự gọi.

1. Khi chúng ta gọi hàm này với số nguyên dương, nó sẽ tự gọi mình bằng cách giảm số.
2. Mỗi hàm nhân số số với giai thừa của số bên dưới nó cho đến khi nó bằng một. Cuộc gọi đệ quy này có thể được giải thích trong các bước sau.
3. Chúng ta hãy xem một hình ảnh hiển thị một quá trình từng bước về những gì đang diễn ra:

Làm việc của một chức năng giai thừa đệ quy

1. Đệ quy của chúng tôi kết thúc khi số lượng giảm xuống 1. cái này được gọi là điều kiện cơ sở.
2. Mỗi chức năng đệ quy phải có một điều kiện cơ sở dừng đệ quy hoặc nếu không thì hàm tự gọi chính nó.
3. Thông dịch viên Python giới hạn độ sâu của đệ quy để giúp tránh các đệ quy vô hạn, dẫn đến tràn chồng.

Đệ quy là quá trình của một hàm tự gọi từ trong mã của chính nó. Bạn có thể nghĩ về nó như một cách khác để hoàn thành một cấu trúc vòng lặp. Mô hình đệ quy xuất hiện trong nhiều tình huống trong thế giới thực, và chúng tôi sẽ bao gồm một số ví dụ về đệ quy trong Python ở đây. Một chức năng đệ quy chỉ tiếp tục tự gọi cho đến khi nó hoàn thành vấn đề trong tay. Điều đó mang lại một điểm tốt, và đó là để đảm bảo rằng chức năng đệ quy của bạn thực sự chấm dứt và trả lại tại một số điểm. Nếu không, chức năng đệ quy sẽ chạy mãi mãi, làm cạn kiệt bộ nhớ của bạn và làm hỏng máy tính của bạn. Có một bước trong đó chức năng thực sự kết thúc được gọi là một điều kiện phá vỡ. Mỗi lần được gọi là hàm đệ quy, các giá trị của các đối số từ cuộc gọi trước được lưu trữ trên ngăn xếp cuộc gọi.

Kiểu đệ quy 1: Đếm ngược vào 2

Ở đây chúng tôi có một hàm có tên BackwardsBy2, in các số theo thứ tự ngược lại bằng cách sử dụng các bước 2 bắt đầu bằng một số ban đầu. Điều kiện phá vỡ là nếu số nhỏ hơn hoặc bằng 0. Trong trường hợp đó, chúng tôi chỉ cần in số 0! Nếu điều kiện đó không được đáp ứng, hàm tự gọi bằng số hiện tại - 2. Chúng tôi cũng khởi tạo danh sách và thêm biểu tượng cảm xúc Smiley bằng số hiện tại. Bằng cách đó, khi việc đếm ngược xảy ra, một số lượng biểu tượng cảm xúc tương ứng sẽ xuất hiện cho mỗi lần lặp. Tôi nghĩ rằng bạn sẽ đồng ý, đây là một tính năng quan trọng của ví dụ đệ quy này.

def backwardsby2[num]:
    if num