[Java] 재귀함수, 꼬리재귀함수

🏃‍♀️·2023년 8월 22일

Java [이론]

목록 보기

3/14

재귀함수

재귀함수란 자기 자신을 다시 호출하는 함수를 말한다.

return 값으로 자기 자신에 대한 연산을 수행한다.

재귀함수가 종료되는 시점을 작성하지 않으면 무한 루프에 빠지게 된다.

메모리 스택 영역을 사용하므로 스택오버플로우가 발생할 수 있다.

예시로 팩토리얼 함수를 작성해보았다.

static int fac1(int num) {
    return num * fac1(num-1);
}

return 부분에 자기 자신에 대한 곱하기 연산을 수행한다.
또한 재귀함수가 종료되는 시점을 작성하지 않았기 때문에 무한 루프에 빠지게 되며 실제로 스택오버플로우가 발생하는 코드이다.

이러한 재귀함수의 문제점에 대응하기 위해서 반복문이나 꼬리 재귀함수를 사용한다.

반복문

반복문을 사용하게 되면 변수를 재사용하고 필요한 부분만 반복 수행하기 때문에 재귀함수에 비해 성능이 좋다.
그러나 코드가 길어지고 복잡해지면서 가독성이 떨어진다.

	재귀함수	반복문
장점	가독성이 좋다.	비교적 성능이 좋다.
단점	메모리를 많이 사용하고 성능이 저하된다.	코드가 복잡해진다.

꼬리재귀함수

꼬리재귀함수란 재귀함수의 장점은 살리고 단점을 보완한 방식이다.
return 부분에서 자기 자신에 대한 연산을 수행하지 않고 오로지 호출만 수행한다.
즉, return address가 필요하지 않아서 스택에 정보를 가지고 있을 필요가 없어진다.

꼬리재귀함수를 사용하기 위해서는 조건이 따른다.
1. 자기 자신에 대한 연산을 수행하지 않을 것 (꼬리재귀방식)
2. 컴파일러가 꼬리재귀 최적화를 지원할 것

꼬리재귀방식의 팩토리얼 구현 코드

    static int fac2(int num){
        if(num == 1) return 1;
        return fac2(num - 1, num * (num -1));
    }

    static int fac2(int num, int acc){
        if(num == 1) return acc;
        return fac2(num - 1, acc * (num - 1));
    }

그러나 자바는 꼬리재귀 최적화를 지원하지 않는다.
JDK 클래스중 보안에 민감한 메소드가 있으며 JDK 라이브러리 코드와 메소드 호출 간 스택 프레임 갯수에 의존한다.
때문에 스택 프레임 수에 변경을 일으키게 되면 의존관계를 망가뜨려 에러가 발생할 수 있다.

꼬리재귀함수 구현하기

JAVA8에서 람다식 함수와 Supplier Class를 통해 꼬리재귀함수를 구현할 수 있다.

추상클래스인 TailCall 생성

public abstract class TailCall<T> {
    public abstract TailCall<T> resume();
    public abstract T eval();
    public abstract boolean isSuspend();
}

하위 클래스 Return, Suspend 생성

public class Suspend<T> extends TailCall<T> {
    private Supplier<TailCall<T>> supplier;
    public T cnt;

    public Suspend(Supplier<TailCall<T>> supplier, T cnt) {
        System.out.println(cnt + ")     Suspend 객체 생성: " + this.toString());
        this.supplier = supplier;
        this.cnt = cnt;
    }

    @Override
    public TailCall<T> resume() {
        Object obj = supplier.get();
        System.out.println(cnt + ")     "+this+".resume()-");
        System.out.println(cnt + ")     supplier.get() 결과 값   : " + obj);
        System.out.println("============================================");
        return (TailCall<T>) obj;
    }

    @Override
    public T eval() {
        throw new IllegalStateException("Suspend has no value");
    }

    @Override
    public boolean isSuspend() {
        return true;
    }
}

public class Return<T> extends TailCall<T> {
    private T t;
    public T cnt;

    public Return(T t, T cnt) {
        this.t = t;
        this.cnt = cnt;
        System.out.println(cnt + ")     Return 객체 생성: " +this);
    }

    @Override
    public TailCall<T> resume() {
        throw new IllegalStateException("Return has no resume");
    }

    @Override
    public T eval() {
        return t;
    }

    @Override
    public boolean isSuspend() {
        return false;
    }
}

main 함수 작성

    public static TailCall<BigInteger> tailFac(BigInteger n, BigInteger acc) {
        return n.min(BigInteger.ONE).equals(n) ? new Return<>(acc,n) : new Suspend<>(() -> tailFac(n.subtract(BigInteger.ONE), n.multiply(acc)), n, acc);
    }

    public static void main(String[] args) {
        TailCall<BigInteger> tailCall = tailFac(BigInteger.valueOf(3), BigInteger.ONE);
        System.out.println("============================================");
        while(tailCall.isSuspend()) {
            System.out.println("  while문에서 tailCall.resume() 호출");
            tailCall = tailCall.resume();
        }
        System.out.println(tailCall.eval());
    }

Supplier Class의 get() 메소드

Supperlier.get()은 매개변수를 받지 않고 리턴 값만 반환하는 메소드이며 지연 로딩을 구현할 수 있다.

실행결과
3) Suspend 객체 생성: Suspend@15aeb7ab
============================================
while문에서 tailCall.resume() 호출
2) Suspend 객체 생성: Suspend@5b6f7412
3) Suspend@15aeb7ab.resume()
3) supplier.get() 결과 값 : Suspend@5b6f7412
============================================
while문에서 tailCall.resume() 호출
1) Return 객체 생성: Return@7530d0a
2) Suspend@5b6f7412.resume()
2) supplier.get() 결과 값 : Return@7530d0a
============================================
6

이걸 실습하면서 이해가 잘 되지 않아서 애먹었다....
특히 supplier.get()을 했을 때 tailCall함수가 실행되는 걸 망각하고 sout으로 출력한다고 한 번 호출하고 return한다고 한 번 더 호출해서 함수가 두번씩 돌아서 정말...
바보같았다.......

맨 앞의 숫자가 팩토리얼 함수에 매개변수로 던진 n이다. 여기서는 3) 이 첫 번째이다.

동작 순서

1) 첫 번째 함수 실행 -> new Suspend<>(Supplier<TailCall<T>>) 첫 번째 객체 생성
2) main 함수의 tailCall에 1의 결과 대입
3) while문 실행
4) tailCall.resume() 호출 -> supplier.get() 호출
5) 1번의 Supplier<TailCall<T>> 생성 -> tailCall() 함수의 결과로 1번과 같은 두 번째 객체 생성
6) return 값이 두 번째 객체의 주소 값이므로 main의 tailCall은 두 번째 객체를 참조하게 됨
7) while문 실행
이 과정이 반복되다가 객체 필드의 isSuspend가 false인 경우 탈출