Konwersja rekurencyjną wdrożenie do realizacji w oparciu pętli

Question

Mam dwa interfejsy, które jest odpowiedzialne za trzyma zamknięcie

Tu jest pierwszy do trzymania zamknięcie, jeśli chodzi o operację mapy.

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

I drugi dla operacji filtrowania

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

Mam klasy o nazwie clist która jest zdolna do pracy z zamknięciami.

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

Oto mój publiczny interfejs implementujący CList z zamknięciami.

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

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

Próbuję przekonwertować funkcji map, który jest realizowany w drodze do cyklicznej pętli while. Nazwałam to maploop. Boli mnie w mózgu przez dwa dni. Każda wskazówka sprawi, że będę bardzo szczęśliwy. Zadaję tutaj to pytanie, ponieważ istnieje prawdopodobieństwo, że ktoś weźmie kurs Daniego Grossmana i zobaczy przykład i spróbuje zaimplementować tę funkcję. Wolę podpowiedź niż rzeczywistą odpowiedź. Dzięki.

Answer 1

Podczas konwersji funkcji rekursywnej na funkcję iteracyjną należy sprawdzić, który stan bez połączenia jest wymagany, jeśli taki istnieje. Następnie utwórz stos i wypchnij stany na stos, i zakoduj go tak, jakbyś w przeciwnym razie pełnił funkcję rekursywną. Jeśli masz wiele wywołań rekursywnych w tej funkcji, będziesz potrzebował nowego elementu stanu, aby zawierał także wartość wskazującą, w którym punkcie funkcji jesteś.

W tym przypadku masz tylko jedno wywołanie rekurencyjne, a jedynym stanem jest xs, więc rzeczy są dość proste i nie potrzebujesz niestandardowego obiektu stanu.

Oto, jak robić rzeczy (nie testowane).

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

Standardowe podejście do przekształcania programu rekursywnego na powtarzalny, odbywa się poprzez wariant rekurencyjny. W bardzo prosty przykład, rozważmy następujący rekurencyjnej funkcji silni, aby obliczyć N!:

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

połączenia factorial(N);.

Making ten ogon rekurencyjnej polega na dodaniu zmiennej Akumulacja:

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

połączenia tailRecursiveFactorial(N, 1);

Ten jest wprost przekształcony do iteracyjnego programu:

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

Oczywiście, problem jest o wiele trudniejsze, ale ogólne podejście powinno nadal działać.