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
Hàm đệ quy Python
Trong Python, chúng ta biết rằng một hàm có thể gọi các hàm khác. Hàm thậm chí có thể gọi chính nó. Các loại cấu trúc này được gọi là hàm đệ quy
Hình ảnh sau đây cho thấy hoạt động của một hàm đệ quy có tên là recurse
Sau đây là một ví dụ về hàm đệ quy để tìm giai thừa của một số nguyên
Giai thừa của một số là tích 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[] là một hàm đệ quy vì nó gọi chính nó
Khi ta gọi hàm này với số nguyên dương thì nó sẽ gọi đệ quy chính nó bằng cách giảm số
Mỗi hàm nhân một 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
Hãy xem một hình ảnh thể hiện quy 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. Đây được gọi là điều kiện cơ bản
Mỗi hàm đệ quy phải có một điều kiện cơ bản để dừng đệ quy, nếu không thì hàm sẽ tự gọi nó vô hạn
Trình thông dịch 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 ngăn xếp
Theo mặc định, độ sâu đệ quy tối đa là 1000. Nếu giới hạn bị vượt qua, kết quả là RecursionError. Hãy xem xét một điều kiện như vậy
Đệ quy là một khái niệm toán học và lập trình phổ biến. Nó có nghĩa là một chức năng gọi chính nó. Điều này có lợi là bạn có thể lặp qua dữ liệu để đạt được kết quả
Nhà phát triển nên rất cẩn thận với đệ quy vì có thể khá dễ dàng viết một hàm không bao giờ kết thúc hoặc một hàm sử dụng quá nhiều bộ nhớ hoặc sức mạnh của bộ xử lý. Tuy nhiên, khi được viết đúng, đệ quy có thể là một cách tiếp cận lập trình rất hiệu quả và thanh lịch về mặt toán học.
Trong ví dụ này, tri_recursion[] là một hàm mà chúng ta đã xác định để gọi chính nó ["recurse"]. Chúng tôi sử dụng biến k làm dữ liệu, giá trị này giảm [-1] mỗi khi chúng tôi lặp lại. Đệ quy kết thúc khi điều kiện không lớn hơn 0 [i. e. khi nó bằng 0]
Đối với một nhà phát triển mới, có thể mất một chút thời gian để tìm ra chính xác cách thức hoạt động của nó, cách tốt nhất để tìm hiểu là thử nghiệm và sửa đổi nó
Chương trình sau chấp nhận một số và chỉ mục từ người dùng. Hàm đệ quy rpower[] sử dụng hai giá trị này làm đối số. Hàm nhân số nhiều lần và đệ quy để trả về lũy thừa
Thí dụ
def rpower[num,idx]:
if[idx==1]:
return[num]
else:
return[num*rpower[num,idx-1]]
base=int[input["Enter number: "]]
exp=int[input["Enter index: "]]
rpow=rpower[base,exp]
print["{} raised to {}: {}".format[base,exp,rpow]]đầu ra
Đây là một lần chạy mẫu -
Enter number: 10 Enter index: 3 10 raised to 3: 1000
Trong chương trình này, chúng tôi đọc giá trị của
The factorial of 3 is 60 và
The factorial of 3 is 61 từ người dùng và sau đó chúng tôi tính toán số mũ cơ sở bằng cách sử dụng hàm đệ quy
The factorial of 3 is 62
Chương trình Python này tính toán số mũ cơ sở bằng cách sử dụng hàm đệ quy
Mã nguồn Python
# power calculation using recursion
# Recursive function definition
def power[x,n]:
if n==0:
return 1
else:
return x * power[x, n-1]
# Reading base and exponent
base = float[input["Enter value of base: "]]
exponent = int[input["Enter value of exponent: "]]
# Function call
result = power[base, exponent]
# Displaying result
print["Result is:", result]
đầu ra
Enter value of base: 2 Enter value of exponent: 3 Result is: 8.0