Java 8 람다 재귀 함수

Java 8을 사용하여 재귀 적 람다 함수 구현

---

Java 8은 람다 함수를 도입했으며 factorial과 같은 것을 구현하고 싶습니다.

 IntToDoubleFunction fact = x -> x == 0 ? 1 : x * fact.applyAsDouble(x-1);

컴파일 반환

  error: variable fact might not have been initialized

함수 자체를 어떻게 참조 할 수 있습니까? 클래스는 익명이지만 인스턴스가 존재합니다 fact.

---

나는 일반적으로 기능 인터페이스 유형의 변수를 래핑하는 일반 도우미 클래스를 사용합니다 (한 번만 정의 된 기능 인터페이스). 이 접근 방식은 지역 변수 초기화 문제를 해결하고 코드가 더 명확하게 보이도록합니다.

이 질문의 경우 코드는 다음과 같습니다.

// Recursive.java
// @param <I> - Functional Interface Type
public class Recursive<I> {
    public I func;
}

// Test.java
public double factorial(int n) {

    Recursive<IntToDoubleFunction> recursive = new Recursive<>();
    recursive.func = x -> (x == 0) ? 1 : x * recursive.func.applyAsDouble(x - 1);

    return recursive.func.applyAsDouble(n);
}

---

한 가지 방법은 helper함수와 숫자를 인수로 사용 하는 보조 함수 를 작성한 다음 실제로 원하는 함수를 작성하는 것 fact = helper(helper,x)입니다.

이렇게 :

BiFunction<BiFunction, Double, Double> factHelper =
        (f, x) -> (x == 0) ? 1.0 : x*(double)f.apply(f,x-1);
Function<Double, Double> fact =
        x -> factHelper.apply(factHelper, x);

이것은 변경 가능한 구조에 대한 참조를 캡처하는 클로저와 같은 코너 케이스 의미론에 의존하거나 "초기화되지 않을 수 있습니다"라는 경고와 함께 자체 참조를 허용하는 것보다 약간 더 우아하게 보입니다.

그래도 Java의 유형 시스템으로 인해 완벽한 솔루션은 아닙니다. 제네릭은 f에 대한 인수가 무한 중첩 제네릭이기 때문에 ,의 인수가 factHelper동일한 유형 factHelper(즉, 동일한 입력 유형 및 출력 유형) 임을 보장 할 수 없습니다 .

따라서 대신 더 안전한 솔루션은 다음과 같습니다.

Function<Double, Double> fact = x -> {
    BiFunction<BiFunction, Double, Double> factHelper =
        (f, d) -> (d == 0) ? 1.0 : d*(double)f.apply(f,d-1);
    return factHelper.apply(factHelper, x);
};

factHelper완벽하지 않은 제네릭 유형 에서 발생하는 코드 냄새 가 이제 람다 내에 포함 (또는 감히 캡슐화)되어 factHelper무의식적으로 호출되지 않도록합니다 .

---

로컬 및 익명 클래스와 람다 는 생성 될 때 값으로 로컬 변수 를 캡처 합니다. 따라서 자신을 가리키는 값이 생성 시점에 아직 존재하지 않기 때문에 지역 변수를 캡처하여 자신을 참조하는 것은 불가능합니다.

로컬 및 익명 클래스의 코드는 this. 그러나 this람다에서 람다를 참조하지 않습니다. 그것은 this외부 범위에서 참조합니다 .

대신 배열과 같은 가변 데이터 구조를 캡처 할 수 있습니다.

IntToDoubleFunction[] foo = { null };
foo[0] = x -> { return  ( x == 0)?1:x* foo[0].applyAsDouble(x-1);};

우아한 해결책은 아니지만.

---

이러한 종류의 작업을 자주 수행해야하는 경우 다른 옵션은 도우미 인터페이스와 메서드를 만드는 것입니다.

public static interface Recursable<T, U> {
    U apply(T t, Recursable<T, U> r);
}

public static <T, U> Function<T, U> recurse(Recursable<T, U> f) {
    return t -> f.apply(t, f);
}

그리고 다음과 같이 작성하십시오.

Function<Integer, Double> fact = recurse(
    (i, f) -> 0 == i ? 1 : i * f.apply(i - 1, f));

(일반적으로 참조 유형을 사용하여이 작업을 수행했지만 기본 버전을 만들 수도 있습니다.)

이것은 이름없는 함수를 만들기 위해 The Little Lisper의 오래된 트릭에서 빌려온 것입니다.

프로덕션 코드에서이 작업을 수행 할 수 있을지 모르겠지만 흥미 롭습니다 ...

---

대답은 다음과 같습니다. applyAsDouble 함수를 호출하는 이름 변수 앞에 this 를 사용해야 합니다.

IntToDoubleFunction fact = x -> x == 0 ? 1 : x * this.fact.applyAsDouble(x-1);

사실을 최종 결정하면 효과가 있습니다.

final IntToDoubleFunction fact = x -> x == 0 ? 1 : x * this.fact.applyAsDouble(x-1);

여기서 기능 인터페이스 UnaryOperator를 사용할 수 있습니다 . 항상 입력 인수를 반환하는 단항 연산자입니다.

1) 이것을 추가 하십시오 . 다음과 같이 함수 이름 앞에

UnaryOperator<Long> fact = x -> x == 0 ? 1  : x * this.fact.apply(x - 1 );

이렇게하면 "정의되기 전에 필드를 참조 할 수 없음" 을 방지 할 수 있습니다.

2) 정적 필드 를 선호하는 경우 ' this '를 클래스 이름으로 바꾸십시오 .

static final UnaryOperator<Long> fact = x -> x== 0? 1: x * MyFactorial.fact.apply(x - 1 );

---

한 가지 해결책은이 함수를 INSTANCE 속성으로 정의하는 것입니다.

import java.util.function.*;
public class Test{

    IntToDoubleFunction fact = x -> { return  ( x == 0)?1:x* fact.applyAsDouble(x-1);};

    public static void main(String[] args) {
      Test test = new Test();
      test.doIt();
    }

    public void doIt(){
       System.out.println("fact(3)=" + fact.applyAsDouble(3));
    }
}

---

재귀를 최적화 할 수 있도록 누산기를 사용하는 또 다른 버전입니다. 일반 인터페이스 정의로 이동했습니다.

Function<Integer,Double> facts = x -> { return  ( x == 0)?1:x* facts.apply(x-1);};
BiFunction<Integer,Double,Double> factAcc= (x,acc) -> { return (x == 0)?acc:factAcc.apply(x- 1,acc*x);};
Function<Integer,Double> fact = x -> factAcc.apply(x,1.0) ;

public static void main(String[] args) {
   Test test = new Test();
   test.doIt();
}

 public void doIt(){
int val=70;
System.out.println("fact(" + val + ")=" + fact.apply(val));
}
}

---

재귀 적 람다를 인스턴스 또는 클래스 변수로 정의 할 수 있습니다.

static DoubleUnaryOperator factorial = x -> x == 0 ? 1
                                          : x * factorial.applyAsDouble(x - 1);

예를 들면 :

class Test {
    static DoubleUnaryOperator factorial = x -> x == 0 ? 1
                                             : x * factorial.applyAsDouble(x - 1));
    public static void main(String[] args) {
        System.out.println(factorial.applyAsDouble(5));
    }
}

인쇄합니다 120.0.

---

public class Main {
    static class Wrapper {
        Function<Integer, Integer> f;
    }

    public static void main(String[] args) {
        final Wrapper w = new Wrapper();
        w.f = x -> x == 0 ? 1 : x * w.f.apply(x - 1);
        System.out.println(w.f.apply(10));
    }
}

---

다음은 작동하지만 신비한 것처럼 보입니다.

import java.util.function.Function;

class recursion{

Function<Integer,Integer>  factorial_lambda;  // The positions of the lambda declaration and initialization must be as is.

public static void main(String[] args) {  new recursion();}

public recursion() {
 factorial_lambda=(i)->{
        if(i==1)
            return 1;
        else
            return i*(factorial_lambda.apply(i-1));
    };
    System.out.println(factorial_lambda.apply(5));
 }
}

// Output 120

---

첫 번째 답변과 조금 비슷합니다 ...

public static Function<Integer,Double> factorial;

static {
    factorial = n -> {
        assert n >= 0;
        return (n == 0) ? 1.0 : n * factorial.apply(n - 1);
    };
}

---

올해 JAX에서 "lambads는 재귀를 지원하지 않는다"고 들었습니다. 이 문장이 의미하는 것은 람다 안의 "this"는 항상 주변 클래스를 참조한다는 것입니다.

그러나 나는 적어도 "재귀"라는 용어를 어떻게 이해하는지-재귀 적 람다를 정의 할 수 있었다.

interface FacInterface {
  int fac(int i);
}
public class Recursion {
  static FacInterface f;
  public static void main(String[] args)
  {
    int j = (args.length == 1) ? new Integer(args[0]) : 10;
    f = (i) -> { if ( i == 1) return 1;
      else return i*f.fac( i-1 ); };
    System.out.println( j+ "! = " + f.fac(j));
  }
}

이 파일을 "Recursion.java"파일에 저장하고 "javac Recursion.java"및 "java Recursion"두 명령을 사용하여 저에게 효과적이었습니다.

clou는 람다가 주변 클래스에서 필드 변수로 구현해야하는 인터페이스를 유지하는 것입니다. 람다는 해당 필드를 참조 할 수 있으며 필드는 암시 적으로 최종적이지 않습니다.

---

또한 크기가 1 인 최종 배열 (예 : Function [])을 생성 한 다음 함수를 요소 0에 할당하여 지역 변수로 정의 할 수도 있습니다. 정확한 구문이 필요한지 알려주세요.

---

람다의 "this"가 포함하는 클래스를 참조한다는 사실을 감안할 때 다음은 오류없이 컴파일됩니다 (물론 종속성이 추가됨).

public class MyClass {
    Function<Map, CustomStruct> sourceToStruct = source -> {
        CustomStruct result;
        Object value;

        for (String key : source.keySet()) {
            value = source.get(key);

            if (value instanceof Map) {
                value = this.sourceToStruct.apply((Map) value);
            }

            result.setValue(key, value);
        }

        return result;
    };
}

---

public class LambdaExperiments {

  @FunctionalInterface
  public interface RFunction<T, R> extends Function<T, R> {
    R recursiveCall(Function<? super T, ? extends R> func, T in);

    default R apply(T in) {
      return recursiveCall(this, in);
    }
  }

  @FunctionalInterface
  public interface RConsumer<T> extends Consumer<T> {
    void recursiveCall(Consumer<? super T> func, T in);

    default void accept(T in) {
      recursiveCall(this, in);
    }
  }

  @FunctionalInterface
  public interface RBiConsumer<T, U> extends BiConsumer<T, U> {
    void recursiveCall(BiConsumer<T, U> func, T t, U u);

    default void accept(T t, U u) {
      recursiveCall(this, t, u);
    }
  }

  public static void main(String[] args) {
    RFunction<Integer, Integer> fibo = (f, x) -> x > 1 ? f.apply(x - 1) + f.apply(x - 2) : x;

    RConsumer<Integer> decreasingPrint = (f, x) -> {
      System.out.println(x);
      if (x > 0) f.accept(x - 1);
    };

    System.out.println("Fibonnaci(15):" + fibo.apply(15));

    decreasingPrint.accept(5);
  }
}

내 테스트 중에 이것은 로컬 재귀 람다에 대해 얻을 수있는 최고입니다. 스트림에서도 사용할 수 있지만 대상 입력의 용이성을 느슨하게합니다.

---

Java 8을 사용한 또 다른 재귀 팩토리얼

public static int factorial(int i) {
    final UnaryOperator<Integer> func = x -> x == 0 ? 1 : x * factorial(x - 1);
    return func.apply(i);
}

---

@IanRobertson 잘하셨습니다. 사실 정적 '팩토리'를 인터페이스 자체의 본문으로 이동하여 전체를 캡슐화 할 수 있습니다.

public static interface Recursable<T, U> {
        U apply(T t, Recursable<T, U> r);

        public static <T, U> Function<T, U> recurseable(Recursable<T, U> f) {
            return t -> f.apply(t, f);
        }
}

이것은 내가 지금까지 본 것 중 가장 깨끗한 솔루션 / 답입니다. 특히 "fact"의 호출이 "자연적으로"작성 되었기 때문에 : fac.apply (n) 이것은 fac (와 같은 단항 함수에 대해 기대하는 것입니다. )

---

문제는 람다 함수가 final변수에서 작동하기를 원하지만 람다 Function로 대체 할 수 있는 가변 참조가 필요하다는 것입니다.

가장 쉬운 트릭은 변수를 멤버 변수로 정의하는 것으로 보이며 컴파일러는 불평하지 않습니다.

어쨌든 여기에서 작업하고 있기 때문에 IntUnaryOperator대신 사용하도록 예제를 변경 했습니다.IntToDoubleFunctionIntegers

import org.junit.Test;
import java.util.function.IntUnaryOperator;
import static org.junit.Assert.assertEquals;

public class RecursiveTest {
    private IntUnaryOperator operator;

    @Test
    public void factorialOfFive(){
        IntUnaryOperator factorial = factorial();
        assertEquals(factorial.applyAsInt(5), 120); // passes
    }

    public IntUnaryOperator factorial() {
        return operator = x -> (x == 0) ? 1 : x * operator.applyAsInt(x - 1);
    }
}

---

다음은 부작용에 의존하지 않는 솔루션입니다. 목적을 흥미롭게 만들기 위해 재귀를 추상화하고 싶다고 가정 해 봅시다 (그렇지 않으면 인스턴스 필드 솔루션이 완벽하게 유효합니다). 트릭은 익명 클래스를 사용하여 'this'참조를 얻는 것입니다.

public static IntToLongFunction reduce(int zeroCase, LongBinaryOperator reduce) {
  return new Object() {
    IntToLongFunction f = x -> x == 0
                               ? zeroCase
                               : reduce.applyAsLong(x, this.f.applyAsLong(x - 1));
  }.f;
}

public static void main(String[] args) {
  IntToLongFunction fact = reduce(1, (a, b) -> a * b);
  IntToLongFunction sum = reduce(0, (a, b) -> a + b);
  System.out.println(fact.applyAsLong(5)); // 120
  System.out.println(sum.applyAsLong(5)); // 15
}

---

이 클래스를 사용하여 재귀 함수를 만들 수 있습니다.

public class Recursive<I> {
    private Recursive() {

    }
    private I i;
    public static <I> I of(Function<RecursiveSupplier<I>, I> f) {
        Recursive<I> rec = new Recursive<>();
        RecursiveSupplier<I> sup = new RecursiveSupplier<>();
        rec.i = f.apply(sup);
        sup.i = rec.i;
        return rec.i;
    }
    public static class RecursiveSupplier<I> {
        private I i;
        public I call() {
            return i;
        }
    }
}

그런 다음 람다와 다음과 같은 기능 인터페이스 정의를 사용하여 단 한 줄로 모든 기능 인터페이스를 사용할 수 있습니다.

Function<Integer, Integer> factorial = Recursive.of(recursive ->
        x -> x == 0 ? 1 : x * recursive.call().apply(x - 1));
System.out.println(factorial.apply(5));

매우 직관적이고 사용하기 쉽습니다.

---

가능한 사용 사례로 피보나치를 사용한 Lambdas에 대한 강의 중에이 질문을 건너 뛰었습니다.

다음과 같이 재귀 람다를 만들 수 있습니다.

import java.util.function.Function;

public class Fib {

   static Function<Integer, Integer> fib;

   public static void main(String[] args) {
       fib = (n) -> { return n > 1 ? fib.apply(n-1) + fib.apply(n-2) : n; };

       for(int i = 0; i < 10; i++){
           System.out.println("fib(" + i + ") = " + fib.apply(i));
       }
   }
}

무엇을 명심해야합니까?

• Lambda는 실행시 평가됩니다.-> 재귀적일 수 있습니다.

• 다른 람다 내부에서 람다 변수를 사용하려면 변수를 초기화해야합니다.-> 재귀 적 람다를 정의하기 전에 foo 값으로 정의해야합니다.

• 람다 내에서 로컬 람다 변수를 사용하려면 변수가 최종이어야하므로 재정의 할 수 없습니다.-> 기본값으로 초기화 된 람다에 클래스 / 객체 변수를 사용합니다

---

여기서 답변의 공통 주제는 람다가 고정 된 참조 포인트 (따라서 @assylias , @Andrey Morozov , @Ian Robertson 등과 같은 클래스 / 인터페이스 기반 답변)가있는 경우 람다가 재귀적일 수 있다는 것 입니다.

멤버 변수 해결 방법으로 @ 000000000000000000000 의 답변을 정말 좋아 했지만 의도 된 람다 함수가 포함하는 함수의 범위에서 다른 변수를 참조하려는 경우 우려가 있습니다. 확실히 할당시 이러한 로컬 참조를 평가하고 결과 함수를 클래스의 다른 메서드에서 액세스 할 수있는 멤버 변수에 넣을 것입니다. 옳지 않은 것 같습니다 (컨테 이닝 메서드 자체가 재귀 적으로 호출되는 경우 매우 흥미로울 수 있습니다).

다음은 OP의 원래 한 줄 람다에 가깝지만 Eclipse가 불평하지 않는 형태로 표현 된 클래스 기반 솔루션의 변형입니다.

IntToDoubleFunction fact = new IntToDoubleFunction() {
    @Override
    public double applyAsDouble(int x) {
        return x == 0 ? 1 : x * this.applyAsDouble(x-1);
    }
};

물론 {}는 익명 클래스를 생성하므로 람다의 평가를위한 참조 포인트가있는 새 범위가 생성되며 함수 자체 범위에 포함되어 있으므로 "형제"변수를 포함한다는 추가 이점이 있습니다.

---

편리한 Java8 컴파일러가 없으므로 내 대답을 테스트 할 수 없습니다. 그러나 '사실'변수를 최종적으로 정의하면 작동할까요?

final IntToDoubleFunction fact = x -> {
    return  ( x == 0)?1:x* fact.applyAsDouble(x-1);
};

참조 URL : https://stackoverflow.com/questions/19429667/implement-recursive-lambda-function-using-java-8