Chức năng Ackermann so với n vòng lặp lồng nhau

Question

Tôi đang làm việc theo cách của mình trên một cuốn sách về tính toán (Minksy 1967) và có một thời gian khó khăn liên quan đến hàm đệ quy với hàm được xác định theo vòng lặp. Cụ ông hỏi để tìm mối quan hệ giữa hai chức năng:

Các Ackermann chức năng (tất cả các mã trong python):

def a(n,m): 
    if n==0: 
     return m+1 
    if m==0: 
     return a(n-1,1) 
    return a(n-1,a(n,m-1)) 

Và một chức năng tính toán với n vòng lồng nhau:

def p(n,m): 
    for i_1 in range(m): 
     for i_2 in range(m): 
      ... 
      for i_n in range(m): 
        m+=1 

Một cách đệ quy để viết điều này (với một vòng lặp) là:

def p(n,m): 
    if n==0: 
     return m+1 
    for i in range(m): 
     m=p(n-1,m) 
    return m 

Hoặc hoàn toàn đệ quy ive cách để viết nó sẽ là:

def p(n,m): 
    return P(n,m,m) 
def P(n,k,m): 
    if n==0: 
     return m+1 
    if k==1: 
     return P(n-1,m,m) 
    m=P(n,k-1,m) 
    return P(n-1,m,m) 

Có cách nào đơn giản hai chức năng này có liên quan? Tôi cảm thấy như tôi đang bò quanh trong sương mù - bất kỳ cái nhìn sâu sắc nào bạn có thể cho tôi cách tiếp cận những loại vấn đề này sẽ được đánh giá cao. Ngoài ra, có cách nào để thực hiện các chức năng vòng lặp đệ quy hoàn toàn mà không có sự giới thiệu của một tham số thứ ba? Cảm ơn.

Answer 1

Uhm ... Tôi không nghĩ rằng điều này sẽ giúp bạn nhiều, tôi cũng khá bối rối, nhưng đây là suy nghĩ của tôi.

• Ackerman (0, m) == p (0, m)
• Ackerman (1, m + 1) == p (1, m)

chỉnh sửa - chờ đợi tôi nghĩ rằng tôi đã làm sai chức năng. Tôi sẽ suy nghĩ thêm sau này, và nếu tôi nghĩ về điều gì đó tôi sẽ cập nhật!