Khái niệm cơ bản về đệ quy bằng Python

Question

"Viết hàm đệ quy", listSum "lấy danh sách các số nguyên và trả về tổng của tất cả các số nguyên trong danh sách".

Ví dụ:

>>>> listSum([1,3,4,5,6]) 
19 

tôi biết làm thế nào để làm điều này một cách khác nhưng không phải theo cách đệ quy.

def listSum(ls): 
    i = 0 
    s = 0 
    while i < len(ls): 
     s = s + ls[i] 
     i = i + 1 
    print s 

Tôi cần cách cơ bản để thực hiện việc này vì các chức năng tích hợp đặc biệt không được phép.

Answer 1

Bất cứ khi nào bạn gặp phải vấn đề như thế này, hãy thử thể hiện kết quả của hàm có cùng chức năng.

Trong trường hợp của bạn, bạn có thể nhận kết quả bằng cách thêm số đầu tiên với kết quả gọi cùng một hàm với phần còn lại của các phần tử trong danh sách.

Ví dụ,

listSum([1, 3, 4, 5, 6]) = 1 + listSum([3, 4, 5, 6]) 
         = 1 + (3 + listSum([4, 5, 6])) 
         = 1 + (3 + (4 + listSum([5, 6]))) 
         = 1 + (3 + (4 + (5 + listSum([6])))) 
         = 1 + (3 + (4 + (5 + (6 + listSum([]))))) 

Bây giờ, những gì cần là kết quả của listSum([])? Nó phải là 0. Điều đó được gọi là điều kiện cơ bản của đệ quy của bạn. Khi điều kiện cơ sở được đáp ứng, đệ quy sẽ kết thúc. Bây giờ, hãy thử thực hiện nó.

Điều chính ở đây là, chia nhỏ danh sách. Bạn có thể sử dụng slicing để thực hiện điều đó.

phiên bản đơn giản

>>> def listSum(ls): 
...  # Base condition 
...  if not ls: 
...   return 0 
... 
...  # First element + result of calling `listsum` with rest of the elements 
...  return ls[0] + listSum(ls[1:]) 
>>> 
>>> listSum([1, 3, 4, 5, 6]) 
19 

---

Tail Gọi Recursion

Một khi bạn hiểu được cách thức hoạt động đệ quy trên, bạn có thể thử để làm cho nó tốt hơn một chút. Bây giờ, để tìm kết quả thực tế, chúng tôi cũng phụ thuộc vào giá trị của hàm trước đó. Câu lệnh return không thể trả về giá trị ngay lập tức cho đến khi cuộc gọi đệ quy trả về kết quả. Chúng ta có thể tránh bằng cách này, đi qua các vãng lai cho các tham số chức năng, như thế này

>>> def listSum(ls, result): 
...  if not ls: 
...   return result 
...  return listSum(ls[1:], result + ls[0]) 
... 
>>> listSum([1, 3, 4, 5, 6], 0) 
19 

Ở đây, chúng tôi vượt qua những gì các giá trị ban đầu của tổng là trong các tham số, đó là zero trong listSum([1, 3, 4, 5, 6], 0). Sau đó, khi điều kiện cơ sở được đáp ứng, chúng tôi đang thực sự tích lũy tổng trong thông số result, vì vậy chúng tôi trả lại. Bây giờ, câu lệnh return cuối cùng có listSum(ls[1:], result + ls[0]), trong đó chúng tôi thêm phần tử đầu tiên vào số result hiện tại và chuyển lại lần nữa cho cuộc gọi đệ quy.

Đây có thể là thời điểm thích hợp để hiểu Tail Call.Nó sẽ không liên quan đến Python, vì nó không làm tối ưu hóa cuộc gọi đuôi.

---

Đi qua xung quanh phiên bản chỉ số

Bây giờ, bạn có thể nghĩ rằng chúng ta đang tạo rất nhiều danh sách trung gian. Tôi có thể tránh điều đó không?

Tất nhiên, bạn có thể. Bạn chỉ cần chỉ mục của mục sẽ được xử lý tiếp theo. Nhưng bây giờ, điều kiện cơ sở sẽ khác. Vì chúng ta sẽ chuyển chỉ mục, chúng ta sẽ xác định cách toàn bộ danh sách đã được xử lý như thế nào? Vâng, nếu chỉ số bằng với độ dài của danh sách, thì chúng tôi đã xử lý tất cả các phần tử trong danh sách.

>>> def listSum(ls, index, result): 
...  # Base condition 
...  if index == len(ls): 
...   return result 
... 
...  # Call with next index and add the current element to result 
...  return listSum(ls, index + 1, result + ls[index]) 
... 
>>> listSum([1, 3, 4, 5, 6], 0, 0) 
19 

---

chức năng Inner phiên bản

Nếu bạn nhìn vào định nghĩa hàm bây giờ, bạn đang đi qua ba thông số với nó. Cho phép nói rằng bạn sẽ phát hành chức năng này như một API. Nó sẽ được thuận tiện cho người dùng để vượt qua ba giá trị, khi họ thực sự tìm thấy tổng của một danh sách?

Không. Những gì chúng tôi có thể làm gì về nó? Chúng ta có thể tạo ra một chức năng, đó là địa phương để thực tế listSum chức năng và chúng ta có thể vượt qua tất cả các thông số thực hiện liên quan đến nó, như thế này

>>> def listSum(ls): 
... 
...  def recursion(index, result): 
...   if index == len(ls): 
...    return result 
...   return recursion(index + 1, result + ls[index]) 
... 
...  return recursion(0, 0) 
... 
>>> listSum([1, 3, 4, 5, 6]) 
19 

Bây giờ, khi listSum được gọi, nó chỉ trả về giá trị trở lại của recursion chức năng bên trong, chấp nhận các thông số index và thông số result. Bây giờ chúng tôi chỉ chuyển những giá trị đó, chứ không phải người dùng của listSum. Họ chỉ phải vượt qua danh sách để được xử lý.

Trong trường hợp này, nếu bạn quan sát các thông số, chúng ta không đi qua ls-recursion nhưng chúng tôi đang sử dụng nó bên trong nó. ls có thể truy cập bên trong recursion vì thuộc tính đóng.

---

Mặc định các thông số phiên bản

Bây giờ, nếu bạn muốn giữ nó đơn giản, mà không cần tạo một chức năng bên trong, bạn có thể tận dụng các thông số mặc định, như thế này

>>> def listSum(ls, index=0, result=0): 
...  # Base condition 
...  if index == len(ls): 
...   return result 
... 
...  # Call with next index and add the current element to result 
...  return listSum(ls, index + 1, result + ls[index]) 
... 
>>> listSum([1, 3, 4, 5, 6]) 
19 

Bây giờ, nếu người gọi không chuyển bất kỳ giá trị nào rõ ràng, thì 0 sẽ được chỉ định cho cả hai index và result.

---

Recursive điện vấn đề

Bây giờ, cho phép áp dụng những ý tưởng cho một vấn đề khác nhau. Ví dụ, hãy thử triển khai hàm power(base, exponent). Nó sẽ trả lại giá trị của base được nâng lên mức exponent.

power(2, 5) = 32 
power(5, 2) = 25 
power(3, 4) = 81 

Bây giờ, làm cách nào chúng ta có thể thực hiện điều này một cách đệ quy? Hãy để chúng tôi cố gắng hiểu những kết quả đó đạt được như thế nào.

power(2, 5) = 2 * 2 * 2 * 2 * 2 = 32 
power(5, 2) = 5 * 5    = 25 
power(3, 4) = 3 * 3 * 3 * 3  = 81 

Hmmm, vì vậy chúng tôi có ý tưởng. Các base nhân với chính nó, exponent lần cho kết quả. Được rồi, làm thế nào để chúng ta tiếp cận nó. Hãy thử xác định giải pháp với cùng chức năng.

power(2, 5) = 2 * power(2, 4) 
      = 2 * (2 * power(2, 3)) 
      = 2 * (2 * (2 * power(2, 2))) 
      = 2 * (2 * (2 * (2 * power(2, 1)))) 

Điều gì sẽ là kết quả nếu bất cứ điều gì được nêu lên quyền lực 1? Kết quả sẽ là cùng một số, phải không? Chúng tôi đã nhận điều kiện cơ sở của chúng tôi cho đệ quy của chúng tôi :-)

  = 2 * (2 * (2 * (2 * 2))) 
      = 2 * (2 * (2 * 4)) 
      = 2 * (2 * 8) 
      = 2 * 16 
      = 32 

Alright, cho phép thực hiện nó.

>>> def power(base, exponent): 
...  # Base condition, if `exponent` is lesser than or equal to 1, return `base` 
...  if exponent <= 1: 
...   return base 
... 
...  return base * power(base, exponent - 1) 
... 
>>> power(2, 5) 
32 
>>> power(5, 2) 
25 
>>> power(3, 4) 
81 

Được rồi, làm cách nào để xác định phiên bản được tối ưu hóa cho cuộc gọi đuôi? Cho phép truyền kết quả hiện tại làm tham số cho chính hàm đó và trả về kết quả khi điều kiện cơ bản mà nó đáp ứng. Hãy giữ cho nó đơn giản và sử dụng phương pháp tham số mặc định trực tiếp.

>>> def power(base, exponent, result=1): 
...  # Since we start with `1`, base condition would be exponent reaching 0 
...  if exponent <= 0: 
...   return result 
... 
...  return power(base, exponent - 1, result * base) 
... 
>>> power(2, 5) 
32 
>>> power(5, 2) 
25 
>>> power(3, 4) 
81 

Bây giờ, chúng tôi sẽ giảm giá trị exponent trong mỗi cuộc gọi đệ quy và nhiều result với base và vượt qua nó để đệ quy power gọi. Chúng tôi bắt đầu với giá trị 1, bởi vì chúng tôi đang tiếp cận vấn đề ngược lại. Các đệ quy sẽ xảy ra như thế này

power(2, 5, 1) = power(2, 4, 1 * 2) 
       = power(2, 4, 2) 
       = power(2, 3, 2 * 2) 
       = power(2, 3, 4) 
       = power(2, 2, 4 * 2) 
       = power(2, 2, 8) 
       = power(2, 1, 8 * 2) 
       = power(2, 1, 16) 
       = power(2, 0, 16 * 2) 
       = power(2, 0, 32) 

Kể từ exponent trở thành số không, điều kiện cơ sở được đáp ứng và result sẽ được trả lại, vì vậy chúng tôi có được 32 :-)

Answer 2

Thoát sớm là điển hình cho các hàm đệ quy. seq là bị lỗi khi trống (do đó khi không có số nào còn lại để tính tổng).

Cú pháp cú pháp cho phép chuyển chuỗi theo thứ tự được gọi là hàm không có số nguyên được tiêu thụ trong bước hiện tại.

def listSum(seq): 
    if not seq: 
     return 0 
    return seq[0] + listSum(seq[1:]) 

print listSum([1,3,4,5,6]) # prints 19 

Answer 3

def listSum(L): 
    """Returns a sum of integers for a list containing 
    integers. 
    input: list of integers 
    output: listSum returns a sum of all the integers 
    in L. 
    """ 
    if L == []: 
     return [] 
    if len(L) == 1: 
     return L[0] 
    else: 
     return L[0] + listSum(L[1:]) 
print listSum([1, 3, 4, 5, 6]) 
print listSum([]) 
print listSum([8])