Chuyển đổi triển khai đệ quy thành triển khai dựa trên vòng lặp

Question

Tôi có hai giao diện chịu trách nhiệm giữ một đóng

Đây là lần đầu tiên để đóng cửa khi hoạt động trên bản đồ.

package com.fs; 

/** 
* This interface is responsible for holding the closures when it comes to map. 
* It uses two generic types. One for the argument and one for the return type. 
* @param <B> Generic type 
* @param <A> Generic type 
*/ 
public interface Func<B,A> { 
    /** 
    * Function prototype m takes an argument of type A and returns a type B. 
    * A map operation can produce a different type. 
    * @param x of type A 
    * @return type B 
    */ 
    B m(A x); 
} 

Và điều thứ hai để lọc các hoạt động

package com.fs; 


/** 
* This interface is responsible for holding the closures when it comes to filter. 
* @param <A> Generic type 
*/ 
public interface Pred<A> { 
    /** 
    * Function prototype m takes an argument of type A and returns a boolean. 
    * A filter operation checks every element if it fits a predicate. 
    * @param x of type A 
    * @return boolean 
    */ 
    boolean m(A x); 
} 

Tôi có một lớp có tên CList có khả năng làm việc với đóng cửa.

package com.impl.list; 

import com.fs.*; 

public class CList<T> { 
    T head; 
    CList<T> tail; 

    public CList(T x, CList<T> xs){ 
     head = x; 
     tail = xs; 
    } 

    static <A,B> CList<B> map(Func<B,A> f, CList<A> xs){ 
     if(xs==null){ 
      return null; 
     } 
     return new CList<>(f.m(xs.head),map(f,xs.tail)); 
    } 

    static <A,B> CList<B> maploop(Func<B,A> f, CList<A> xs){ 
     //????? 
     return null; 
    } 

    static <A> CList<A> filter(Pred<A> f, CList<A> xs){ 
     if(xs == null){ 
      return null; 
     } 
     if(f.m(xs.head)){ 
      return new CList<>(xs.head, filter(f,xs.tail)); 
     } 
     return filter(f,xs.tail); 
    } 

    static <A> int length(CList<A> xs){ 
     int ans =0; 
     while(xs!= null){ 
      ++ans; 
      xs=xs.tail; 
     } 
     return ans; 
    } 
} 

Đây là giao diện công khai của tôi triển khai CLIST với bao đóng.

package com.impl.list; 

import com.fs.Func; 
import com.fs.Pred; 

public class CListClient { 
    public static CList<Integer> doubleAll(CList<Integer> xs){ 
     Func<Integer, Integer> df = new Func<Integer, Integer>() { 
      @Override 
      public Integer m(Integer x) { 
       return x * 2; 
      } 
     }; 

     return CList.map(df, xs); 
    } 

    public static int countNs(CList<Integer> xs,final int n){ 
     Pred<Integer> pf = new Pred<Integer>() { 
      @Override 
      public boolean m(Integer x) { 
       return x==n; 
      } 
     }; 
     return CList.length(CList.filter(pf, xs)); 
    } 

    public static CList<Integer> doubleAllloop(CList<Integer> xs){ 
     Func<Integer, Integer> df = new Func<Integer, Integer>() { 
      @Override 
      public Integer m(Integer x) { 
       return x * 2; 
      } 
     }; 

     return CList.maploop(df, xs); 
    } 
} 

Và một thử nghiệm đơn giản:

package basic; 


import com.impl.list.CList; 
import com.impl.list.CListClient; 
import org.junit.Test; 


public class ListTester { 

    CList<Integer> intlist_1 = new CList<>(new Integer(1),null); 
    CList<Integer> intlist_2 = new CList<>(new Integer(2),intlist_1); 
    CList<Integer> intlist_3 = new CList<>(new Integer(3),intlist_2); 
    CList<Integer> intlist_4 = new CList<>(new Integer(4),intlist_3); 
    CList<Integer> intlist_5 = new CList<>(new Integer(4),intlist_4); 
    CList<Integer> intlist = new CList<>(new Integer(5),intlist_5); 

    @Test 
    public void test_doubleAll(){ 
     CList<Integer> doubled = CListClient.doubleAll(intlist); 
     CList<Integer> doubledloop = CListClient.doubleAllloop(intlist); 

    } 

    @Test 
    public void test_CountNs(){ 
     int count3s = CListClient.countNs(intlist, 3); 
    } 
} 

Tôi cố gắng để chuyển đổi các chức năng bản đồ được thực hiện theo một cách đệ quy cho một vòng lặp while. Tôi đặt tên nó là maploop. Nó làm tổn thương não của tôi trong hai ngày. Mọi gợi ý sẽ khiến tôi rất hạnh phúc. Tôi đang hỏi câu hỏi này ở đây vì có khả năng ai đó có thể tham gia khóa học Dan Grossman và xem ví dụ và cố gắng thực hiện chức năng đó. Tôi thích một gợi ý hơn là một câu trả lời thực tế. Cảm ơn.

Answer 1

Khi chuyển đổi hàm đệ quy thành hàm lặp, bạn phải kiểm tra trạng thái cuộc gọi không đuôi nào là bắt buộc, nếu có. Sau đó tạo một ngăn xếp và đẩy các trạng thái lên ngăn xếp, và mã hóa nó giống như bạn sẽ làm hàm đệ quy khác. Nếu bạn có nhiều cuộc gọi đệ quy trong hàm, bạn sẽ cần mục trạng thái mới của bạn cũng chứa một giá trị cho biết bạn đang ở đâu tại thời điểm nào.

Trong trường hợp này, bạn chỉ có một cuộc gọi đệ quy và trạng thái duy nhất là xs, vì vậy mọi thứ khá đơn giản và bạn không cần đối tượng trạng thái tùy chỉnh.

Đây là cách tôi làm mọi thứ (không được kiểm tra).

static <A,B> CList<B> maploop(Func<B,A> f, CList<A> xs){ 
    Stack<CList<A>> stack = new Stack<>(); 

    while(xs != null){ 
     stack.push(xs); 
     xs = xs.tail; 
    } 

    CList<a> result = xs; 

    while(!stack.empty()){ 
     xs = stack.pop(); 
     result = new CList<>(f.m(xs.head), result); 
    } 

    return result; 
}  

Answer 2

Cách tiếp cận chuẩn để chuyển đổi chương trình đệ quy sang chương trình lặp lại, thông qua biến thể đệ quy đuôi. Như một ví dụ rất đơn giản, hãy xem xét các chức năng thừa đệ quy sau đây, để tính toán N!:

int factorial(int x) { 
    if (x == 0) 
     return 1; 
    else 
     return x * factorial(x-1); 
} 

Gọi factorial(N);.

Làm này đuôi-đệ quy liên quan đến việc bổ sung thêm một biến tích lũy:

int tailRecursiveFactorial(int x, int y) { 
    if (x == 0) 
     return y; 
    else 
     return tailRecursiveFactorial(x-1, x*y); 
} 

Gọi tailRecursiveFactorial(N, 1);

một này được thẳng thắn chuyển thành một chương trình lặp đi lặp lại:

int x = N; 
int y = 1; 
while (x != 0) { 
    y = x*y; 
    x = x-1; 
} 

Tất nhiên, vấn đề của bạn là một việc tốt hơn, nhưng cách tiếp cận chung vẫn nên hoạt động.