轉換一個遞歸實現到基於循環實現

Question

我有兩個接口，它負責保持閉合

這是第一個用於保持關閉，當涉及到一個地圖操作。

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); 
} 

，第二個用於過濾操作

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); 
} 

我有一個名爲欄列表類，這是能夠與關閉工作。

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; 
    } 
} 

這是我的公開接口實現閉包CList。

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); 
    } 
} 

和一個簡單的測試：

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); 
    } 
} 

我想轉換其在遞歸的方式與while循環實現的地圖功能。我將它命名爲maploop。它傷害了我的大腦兩天。任何暗示都會讓我很開心。我在這裏問這個問題，因爲有人可能會採取丹格羅斯曼的課程，看看這個例子並嘗試實現這個功能。我更喜歡暗示而不是實際的答案。 謝謝。

Answer 1

將遞歸函數轉換爲迭代函數時，必須檢查需要哪個非尾部調用狀態（如果有）。然後創建一個堆棧並將這些狀態推送到堆棧上，然後像遞歸函數那樣對其進行編碼。如果函數中有多個遞歸調用，則需要新的狀態項還包含一個值，指示函數中的哪一點。

在這種情況下，你只有一個遞歸調用，唯一的狀態是xs，所以事情很簡單，你不需要自定義狀態對象。

以下是我如何做事情（未經測試）。

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

將遞歸程序轉換爲迭代程序的標準方法是通過尾遞歸變體。作爲一個非常簡單的例子，考慮下面的遞歸階乘函數，計算N!：

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

呼叫factorial(N);。

讓該尾遞歸涉及添加的累積變量：

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

呼叫tailRecursiveFactorial(N, 1);

這一個是直接地轉化爲一個迭代程序：

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

當然，你的問題是一件很難的事情，但總的方法仍然有效。