java - Converting a recursive implementation to a loop based implementation -

i have 2 interfaces responsible holding closure

here first 1 holding closure when comes map operation.

package com.fs;  /**  * interface responsible holding closures when comes map.  * uses 2 generic types. 1 argument , 1 return type.  * @param <b> generic type   * @param <a> generic type  */ public interface func<b,a> {     /**      * function prototype m takes argument of type , returns type b.      * map operation can produce different type.      * @param x of type      * @return type b      */      b m(a x);  } 

and second 1 filtering operations

package com.fs;   /**  * interface responsible holding closures when comes filter.  * @param <a> generic type   */ public interface pred<a> {     /**      * function prototype m takes argument of type , returns boolean.      * filter operation checks every element if fits predicate.      * @param x of type      * @return boolean      */     boolean m(a x); } 

i have class named clist capable of working closures.

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

here public interface implementing clist closures.

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

and simple tester:

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

i trying convert map function implemented in recursive way while loop. named maploop. hurts brain 2 days.any hint make me happy.i asking question here since there probability may take dan grossman course , see example , try implement function. prefer hint actual answer. thanks.

when converting recursive function iterative function, have examine non tail call state required, if any. create stack , push states onto stack, , code recursive function otherwise. if have multiple recursive calls in function, you'll need new state item contain value indicating @ point in function are.

in case, have 1 recursive call, , state xs, things pretty simple , don't need custom state object.

here's how i'd things (not tested).

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