재귀 함수 - JAVA

재귀 함수

자기 자신을 호출하는 함수

스택 자료구조를 이용한다. 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.(선입후출, First In Last Out)
따라서 스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현될 수 있다. DFS가 대표적인 예시이다.

2가지 방식으로 구현한 팩토리얼 예제

// 반복으로 구현한 팩토리얼
public function int iterative(int n) {
	int result = 0;
    for(int i=0; i < n; i++){
    	result += i;
    }
    return i;
}

// 재귀적으로 구현한 팩토리얼
public function recursive(int n){
	//종료 조건
	if(n <= 1){
    	return 1;
    }
    //n! = n * (n-1)!를 그대로 코드로 작성
    return n * recursive(n-1);
}

반복문을 사용하는 경우보다 재귀함수를 사용하게 되면, 수학의 점화식을 사용할 수 있으므로, 더 간결한 코드를 짤 수 있다.
재귀식을 사용할 경우, 무한루프를 방지하기 위해, 꼭 종료조건을 명시한다.