재귀함수란?

재귀함수는 내가 나를 참조하는 함수.
가장 대표적인 것은 (오늘 내가 못 풀었던^^..) 팩토리얼

팩토리얼

팩토리얼은 중학교때? 배우는 수학적 개념으로 5!이면 5부터 1까지를 순서대로 곱하는 연산이다.
예를 들어, 5!는 12345, 즉 120이다.

팩토리얼은 주로 경우의 수를 구하는데 사용된다.
n개의 색깔을 나열하는 경우의 수를 구하려면 n!을 하면 된다.

이걸 for문을 써서 먼저 코드로 구현하게 되면

public static int fact(int n) {
    int result = 1;
    
    for(int i = 1; i<=n ; i++) {
        result *= i;
    }
    
    return result;
};

 public static int fact(int n) {
        if(n<=1)
            return 1;
        else
            return fact(n-1)*n;
    }

이런 식으로 구현될 수 있다.
이런 식으로 함수 안에서 나 자신을 다시 참조하는 것을 재귀함수라고 한다.

이렇게 간단한 건데 왜 못했을까?ㅠㅠ
흑흑..

예를 들어, fact(5);를 실행한다고 치면

n=5

else문을 타고 fact(4) x 5이 return 된다.
그러면 그 안에서 fact(4)가 다시 실행되므로

n=4

가 되고 else문을 타고 다시
fact(3)x4x5

...

이런 식으로

n=2

까지 진행되고,

n=1

이 되면 n만 return이 되기 때문에,
결과적으로는
1x2x3x4x5 연산이 실행 되는 것이다.

재귀의 기본 개념은

문제의 범위보다 약간 좁은 하위 문제를 해결하고, 이 답을 이용하여 원래 문제를 해결하는 것

직접 재귀와 간접 재귀

• 직접 재귀: 자기 자신과 같은 메서드를 호출하는 것

a() {
	a();
}

• 간접 재귀: 다른 메서드를 통해 자기 자신과 같은 메서드를 호출하는 것

b() {
	a();
}

a() {
	b();
}

스택 프레임으로 재귀함수 이해하기

자바 메모리 구조에서 메서드는 Stack에 올라가게 된다.

재귀 함수의 예제 중에 N을 넣으면 1부터 N까지 숫자를 모두 출력하는 함수를 작성한다고 치면,

public void DFS(int n) {
	if(n==0) return;
	else {
		DFS(n-1);
        System.out.print(n + " ");
	}
}

으로 작성할 수 있다.

여기서 System.out.print()가 함수 위에 있는지,
아래 있는지에 따라 숫자의 출력 순서가 반대가 되는데 이를 이해하려면 Stack Frame의 구조를 이해해야 한다.

Stack은 모두 알다시피, First In Last Out 구조로 되어있다.

Main 메서드에서 DFS (3)을 호출했을 때,
Stack에는 else 문을 타고

Stack Frame
DFS(1)
DFS(2)
DFS(3)

이런 식으로 쌓이게 된다.

들어갈 때는 DFS(3)부터 순서대로 쌓이고 System.out.print()는 보류가 된 상태이며, 모두 쌓이게 된 후에 DFS(1) 부터 차례대로 출력 함수가 실행되며 Pop　되는 것이다.

그러면 실제 출력은

1 2 3

이런 식으로 출력되게 된다.