Đệ quy trực tiếp trong Python là gì?

Một hàm được gọi là đệ quy đuôi, nếu không có thao tác nào đang chờ xử lý khi hàm đệ quy trả về trình gọi của nó

• Các hàm như vậy, ngay lập tức trả về giá trị trả về từ hàm gọi
• Đây là một phương pháp hiệu quả so với các phương pháp khác, vì không gian ngăn xếp cần thiết ít hơn và thậm chí chi phí tính toán sẽ giảm xuống
• Nhớ lại ví dụ đã thảo luận trước đây, giai thừa của một số. Chúng tôi đã viết nó theo cách đệ quy không theo đuôi, vì hoạt động sau cuộc gọi vẫn đang chờ xử lý

#include 

int fact(int n)
{
  if (n == 1)
    return 1;
  else
    return (n * fact(n - 1));
}

int main()
{
  int num = 5;
  std::cout << fact(num) << std::endl;
  return 0;
}

Để làm cho nó đệ quy đuôi, thông tin về các tác vụ đang chờ xử lý phải được theo dõi

#include 

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

Nếu bạn quan sát, 'fact2' có cú pháp tương tự như fact ban đầu. Bây giờ, 'thực tế' trong trường hợp đệ quy đuôi không có các phép tính/hoạt động đang chờ xử lý để thực hiện khi trả về từ các lệnh gọi hàm đệ quy
Giá trị được tính bởi fact2 được trả về đơn giản. Do đó, lượng không gian cần thiết trên ngăn xếp giảm đáng kể. (chỉ dành cho giá trị của n và kết quả, cần có khoảng trống

Đệ quy tuyến tính và cây

Tùy thuộc vào cấu trúc, các cuộc gọi hàm đệ quy thực hiện hoặc phát triển, nó có thể là tuyến tính hoặc phi tuyến tính
Đó là đệ quy tuyến tính khi, các hoạt động đang chờ xử lý không liên quan đến một lệnh gọi đệ quy khác đến hàm. Hàm đệ quy giai thừa của chúng tôi là đệ quy tuyến tính vì nó chỉ liên quan đến việc nhân các giá trị được trả về và không có lệnh gọi hàm nào nữa
Đệ quy cây là khi, các hoạt động đang chờ xử lý liên quan đến một lệnh gọi hàm đệ quy khác
Ví dụ –  Chuỗi Fibonacci, các hoạt động đang chờ xử lý có lệnh gọi đệ quy đến hàm đệ quy fib() để tính toán kết quả

Khi nào không sử dụng đệ quy?

Về cơ bản, bất kỳ vấn đề nào có thể được giải quyết bằng đệ quy cũng có thể được giải quyết bằng phép lặp. Mặc dù đối với một số ứng dụng nhất định như Tháp Hà Nội, một số vấn đề về trí tuệ nhân tạo, v.v., đệ quy được sử dụng vì nó xác định vấn đề một cách tự nhiên, nhưng vẫn có những thời điểm nhất định không nên sử dụng đệ quy

Đệ quy trong Python hoặc bất kỳ ngôn ngữ lập trình nào khác là một quá trình trong đó một hàm gọi chính nó một hoặc nhiều lần trong phần thân của nó. Nó có thể gọi chính nó trực tiếp hoặc gián tiếp

Nếu bất kỳ định nghĩa hàm nào đáp ứng điều kiện của đệ quy, chúng tôi gọi nó là hàm đệ quy

Hàm đệ quy là hàm gọi hoặc gọi chính nó ít nhất một lần trong phần thân của nó. Thông thường, giá trị trả về là giá trị trả về của lệnh gọi hàm

Hàm đệ quy về cơ bản là một chuỗi các hàm gọi đến cùng một hàm. Nó hoạt động giống như vòng lặp, có hoặc không có điều kiện kết thúc. Nó gọi chính nó, trực tiếp hoặc gián tiếp, thông qua một chức năng khác

Một ví dụ nổi tiếng thường được sử dụng để mô tả đệ quy trong Python hoặc các ngôn ngữ lập trình khác là phép tính giai thừa (giai thừa cho giá trị 6 là 6 * 5 * 4 * 3 * 2 * 1)

Đệ quy trong Python là một kỹ thuật cơ bản và rất hiệu quả của lập trình máy tính được sử dụng để giải quyết một loại vấn đề lập trình phức tạp cụ thể. Nó phù hợp nhất khi chúng ta cần gọi lặp đi lặp lại cùng một phương thức với các tham số khác nhau

Đệ quy cung cấp một số lợi thế cho các lập trình viên, chẳng hạn như để phát triển mã sạch và ngắn và cũng giúp lập trình viên tránh các vòng lặp

Đôi khi, khái niệm đệ quy có thể hơi khó hiểu đối với người mới bắt đầu. Nhưng, sự thật là chúng ta có thể dễ dàng giải quyết nhiều vấn đề lập trình phức tạp với sự trợ giúp của kỹ thuật đệ quy

Một số bài toán tính toán như tháp Hà Nội, DFS, duyệt cây, quay lui, v.v. mà các kỹ thuật khác có thể giải quyết được giải quyết tốt hơn bằng đệ quy

Cú pháp đệ quy trong Python

---

Trong Python, chúng ta có thể chia cú pháp đệ quy thành hai loại

• đệ quy trực tiếp
• đệ quy gián tiếp

Đệ quy trực tiếp . Nó xảy ra khi một chức năng gọi chính nó trực tiếp từ bên trong cơ thể của chính nó. Cú pháp cơ bản để khai báo một hàm đệ quy trong Python tự gọi trực tiếp như sau.

def recursiveFunction(param):
  # function code
    recursiveFunction(param) # recursive call.

recursiveFunction(arg) # function calling with passing argument values.

Trong cú pháp trên, recursiveFunction() là một hàm đệ quy đang gọi chính nó bên trong hàm. Nhìn vào hình bên dưới minh họa hoạt động đơn giản của đệ quy trong Python

Hãy lấy một ví dụ đơn giản dựa trên đệ quy trực tiếp

def recursiveFunction():
    print('Hello')
    recursiveFunction() # recursive call.
recursiveFunction() # calling function.

Output:
      Hello
      Hello
      . . .

Đệ quy gián tiếp . Đệ quy này xảy ra khi một hàm gọi một hàm khác, đổi lại hàm này sẽ gọi lại hàm đó.

Ví dụ khi hàm A gọi hàm B khác và hàm B gọi hàm A thì ta gọi đó là cách gọi gián tiếp. Cú pháp cơ bản để khai báo một hàm đệ quy gọi chính nó một cách gián tiếp nhiều lần như sau.

def A_function(parameter):
  # function code.
    B_function(parameter)

def B_function(parameter):
  # function code.
    A_function(parameter)

Hãy lấy một mã ví dụ đơn giản dựa trên lệnh gọi đệ quy gián tiếp

def A_function():
    print('A')
    B_function() # recursive call.

def B_function():
    print('B')
    A_function() # recursive call.
A_function() # function calling.

Output:
       A
       B
       A
       B
       . .
       . .

Như bạn sẽ thấy khi thực thi đoạn mã đệ quy trên trên bàn điều khiển, đoạn mã này đang thực thi vô thời hạn. Cuối cùng, trình thông dịch Python tạo ra lỗi (RecursionError. vượt quá độ sâu đệ quy tối đa trong khi gọi một đối tượng Python). Để khắc phục vấn đề này, chúng ta cần chấm dứt đệ quy. Hãy hiểu nó

Làm cách nào để dừng đệ quy trong Python?

---

Khi định nghĩa hàm đệ quy trong Python hoặc các ngôn ngữ lập trình khác, cần chỉ định điều kiện kết thúc. Nếu chúng tôi đặt điều kiện kết thúc trong đệ quy, điều đó có nghĩa là mã đang hoạt động bình thường. Nếu chúng ta không đặt điều kiện như vậy, thì có thể xảy ra lệnh gọi “hàm” vô hạn

Vì lý do này, chúng ta cần chỉ định một điều kiện để kết thúc đệ quy. Điều kiện này được gọi là trường hợp cơ sở hoặc điểm dừng

Trường hợp cơ sở hoặc trường hợp đầu cuối là điều kiện ngăn chặn đệ quy vô hạn. Trong trường hợp thiết bị đầu cuối, không có lời gọi hàm đệ quy nào xảy ra. Không có trường hợp đầu cuối, chúng ta không bao giờ có thể dừng việc thực thi hàm đệ quy

Một hàm đệ quy được xác định rõ phải thỏa mãn hai điều kiện là

• Phải có trường hợp cơ sở để hàm không gọi chính nó là vô hạn lần
• Trong mọi cuộc gọi hoặc lần lặp, đối số sẽ tiến gần hơn đến trường hợp cơ sở thông qua quan hệ lặp lại, tạo ra một giải pháp mới từ giải pháp trước đó

Xem xét mã ví dụ sau được đưa ra bên dưới, trong đó chúng tôi sẽ hiển thị một thông báo bốn lần bằng phương pháp đệ quy

ví dụ 1.

count = 0
def display():
    global count
    count += 1
    if count <= 4: # base case.
        print("Hello world")
        display() # recursive call.
display() # normal method call.

Output:
      Hello world
      Hello world
      Hello world
      Hello world

Trong đoạn mã chương trình trên, chúng ta đã sử dụng một “câu lệnh if” có điều kiện trong thân hàm để kiểm tra số đếm có nhỏ hơn 4 không. Đây là điều kiện cơ bản

Miễn là điều kiện này còn đúng, hàm đệ quy display() sẽ tự gọi. Trên mỗi lần lặp, số đếm tăng thêm 1 và hàm display() được gọi cho đến khi số đếm bằng bốn

Khi đếm đến 5, câu lệnh điều kiện đánh giá là sai. Vì điều kiện cơ sở đã thỏa mãn nên hàm sẽ không gọi nữa

ví dụ 2

Hãy viết một chương trình rất đơn giản để in các số đếm ngược từ 5 đến 1 dựa trên đệ quy

def countDown(num):
# Displaying the number.
    print(num, end= " ")
# Decreasing the number value by 1.
    newNum = num - 1
# Base case or stopping point.
    if newNum > 0:
        countDown(newNum)
countDown(5) # calling function.

Output:
       5 4 3 2 1

Trong đoạn mã chương trình trên, chúng ta đã chuyển số 5 làm đối số trong khi gọi một hàm. Bên trong thân hàm, chúng ta đã sử dụng một “câu lệnh if” có điều kiện để kiểm tra xem đối số được truyền vào có lớn hơn 0 không. Đây là điều kiện cơ bản

Miễn là Python đánh giá điều kiện này là đúng, thì hàm đệ quy CountDown() sẽ tự gọi. Trên mỗi lần lặp, giá trị số giảm đi 1 và hàm countDown() được gọi cho đến khi số dương

Xem các bước sau để hiểu rõ các cuộc gọi đệ quy

• CountDown(5) in 5 và gọi CountDown(4)
• CountDown(4) in 4 và gọi CountDown(3)
• CountDown(3) in 3 và gọi CountDown(2)
• đếmDown(2) in 2 và gọi đếmDown(1)
• đếmDown(1) in 1 và gọi đếmDown(0)

Khi số đạt đến 0, "câu lệnh if" có điều kiện đánh giá là sai. Vì điều kiện cơ sở được đáp ứng, chức năng không được gọi nữa

ví dụ 3

Viết chương trình đếm ngược các số đến 0 bằng phương pháp đệ quy

def recursiveFunction():
    print('Hello')
    recursiveFunction() # recursive call.
recursiveFunction() # calling function.

0

def recursiveFunction():
    print('Hello')
    recursiveFunction() # recursive call.
recursiveFunction() # calling function.

1

Lưu ý . Nếu chúng ta thực hiện một lời gọi đệ quy bên trong khối if, thì khối other sẽ chứa logic của điều kiện cơ sở. Nếu chúng ta thực hiện lời gọi đệ quy bên trong khối other, khối if sẽ chứa logic của điều kiện cơ sở.

Các loại đệ quy trong Python

---

Có hai loại đệ quy trong Python. họ đang

• đệ quy đầu
• đệ quy đuôi

Hãy hiểu từng cái một với sự trợ giúp của các ví dụ

đệ quy đầu

Trong kiểu đệ quy này, lời gọi đệ quy xảy ra trước các xử lý khác trong hàm. Ví dụ

def recursiveFunction():
    print('Hello')
    recursiveFunction() # recursive call.
recursiveFunction() # calling function.

2_______3_______3

Trong mã chương trình trên, đầu tiên các cuộc gọi đệ quy xảy ra và sau đó quá trình in diễn ra. Do đó, giá trị cuối cùng của num, i. e. 1, được hiển thị đầu tiên. Do đó, số in theo thứ tự từ 1 đến 6

đệ quy đuôi

Trong loại đệ quy này, quá trình xử lý xảy ra trước khi gọi đệ quy. Đệ quy đuôi hoạt động giống như một vòng lặp trong đó hàm thực thi tất cả các câu lệnh trước khi gọi đệ quy. Hãy lấy một ví dụ dựa trên nó

def recursiveFunction():
    print('Hello')
    recursiveFunction() # recursive call.
recursiveFunction() # calling function.

4_______3_______5

Trong mã chương trình này, quá trình in đầu tiên diễn ra và sau đó xảy ra lệnh gọi đệ quy. Do đó, giá trị đầu tiên của n, i. e. 1, được hiển thị đầu tiên trên bảng điều khiển. Do đó, các số in theo thứ tự từ 1 đến 10

Chương trình giai thừa sử dụng đệ quy trong Python

---

Sau đây, chúng ta sẽ tìm hiểu cách tính giai thừa của một số bằng phương pháp đệ quy. Giai thừa của một số là tích của số đó với tất cả các số nguyên dương đứng sau nó. Chúng tôi đại diện cho nó như là n

Ví dụ: giai thừa của số 4 được biểu thị bằng 4. Nó bằng 4 * 3 * 2 * 1, kết quả là 24. Các bước cơ bản để tính giai thừa của bất kỳ số n nào, như sau

(n) * (n – 1) * (n – 2) * (n – 3) *. . . . . * 1

Trước hết hãy viết chương trình tính giai thừa của một số bằng vòng lặp for

Mã chương trình

def recursiveFunction():
    print('Hello')
    recursiveFunction() # recursive call.
recursiveFunction() # calling function.

6

def recursiveFunction():
    print('Hello')
    recursiveFunction() # recursive call.
recursiveFunction() # calling function.

7

Trong đoạn mã chương trình trên, chúng tôi đã lấy số 7 làm đầu vào từ người dùng và lưu trữ nó trong một biến num. Sau đó, chúng ta đã gọi hàm bằng cách truyền giá trị của biến num

Bên trong hàm, chúng tôi đã kiểm tra xem số đó là âm, 0 hay dương bằng cách sử dụng câu lệnh if elif other. Bên trong khối other, chúng ta đã sử dụng hàm for loop và range() để tính giai thừa của một số. Nhìn vào các bước sau trong bảng dưới đây

Phép lặp * i (giá trị trả về)i = 11 * 1 = 1i = 21 * 2 = 2i = 32 * 3 = 6i = 43 * 4 = 24

Giai thừa của một số bằng phương pháp đệ quy

Bây giờ hãy viết mã để tính giai thừa của một số bằng cách sử dụng đệ quy

Mã chương trình

def recursiveFunction():
    print('Hello')
    recursiveFunction() # recursive call.
recursiveFunction() # calling function.

8

def recursiveFunction():
    print('Hello')
    recursiveFunction() # recursive call.
recursiveFunction() # calling function.

9

Trong chương trình trên, fact() là một hàm đệ quy, vì nó gọi chính nó. Khi chúng ta gọi hàm này bằng cách chuyển giá trị dương làm đối số, nó sẽ tự gọi đệ quy bằng cách giảm số

Mỗi lệnh gọi hàm đệ quy nhân một số với giai thừa của (số – 1) cho đến khi số đó bằng 1. Khi số bằng 1, đệ quy kết thúc. Đây là điều kiện cơ bản

Mỗi hàm đệ quy phải có một điều kiện cơ sở để ngăn đệ quy vô hạn. Nhìn vào các bước dưới đây của các cuộc gọi đệ quy

• fact(5) – Lần gọi đầu tiên với 5
• 5 * fact(4) – Lần gọi thứ 2 với 4
• 5 * 4 * fact(3) – Lần gọi thứ 3 với 3
• 5 * 4 * 3 * fact(2) – Cuộc gọi thứ 4 với 2
• 5 * 4 * 3 * 2 * fact(1) – Lần gọi thứ 5 với 1
• 5 * 4 * 3 * 2 * 1 – quay lại từ cuộc gọi thứ 5 khi số bằng 1

Lúc đầu, bạn có thể thấy rằng hiểu logic của hàm đệ quy khó hơn, nhưng chúng sẽ trở nên dễ dàng hơn khi thực hành một số chương trình

Ưu điểm của đệ quy trong Python

---

Có những ưu điểm sau khi sử dụng kỹ thuật đệ quy trong lập trình Python. Họ như

• Sử dụng đệ quy, chúng ta có thể chia hàm thành các bài toán con nhỏ hơn
• Nó cho phép chúng ta chia nhiệm vụ phức tạp thành các nhiệm vụ đơn giản hơn
• Sử dụng hàm đệ quy làm cho mã có vẻ đơn giản và hiệu quả vì chúng ta cần viết ít dòng mã hơn

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

---

Ngoài nhiều ưu điểm của việc sử dụng đệ quy, cũng có những nhược điểm sau khi sử dụng nó trong lập trình Python. Họ như

Đệ quy trực tiếp là gì?

Đệ quy trực tiếp và gián tiếp là gì?

Hai loại đệ quy Python là gì?

Các loại đệ quy trực tiếp là gì?