转换一个递归实现到基于循环实现

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

当然，你的问题是一件很难的事情，但总的方法仍然有效。