재귀 알고리즘 분석 [자바]

재귀란?

 

자신을 정의할 때 자기 자신을 재참조하는 방법이다.

---

알고리즘을 작성할 때 재귀를 이용하여 복잡한 로직을 쉽게 구현할 수 있다.

 

이렇게 정의한 경우 재귀적(recursive)이라고 한다.

 

팩토리얼

재귀의 예로 가장 많이 소개되는 팩토리얼이다.

 

public int factorial(int n){
	if(n > 0){
    	return n * factorial(n-1);
    }else{
    	return 1;
    }
}

 

위와 같이 factorial 함수를 정의할 때 자기 자신을 재참조하여 작성할 수 있다.

---

재귀 호출

위 factorial 함수에 3을 대입하여 예시 코드가 어떻게 호출되는지 확인해 보자.

 

         n = 3
           ↓
factorial(3) 호출
  ↓
if( 3 > 0 ) return 3 * factorial( 3 - 1 );
    ↙ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ↙                                  
if( 2 > 0 ) return 2 * factorial( 2 - 1 );
    ↙ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ↙
if( 1 > 0) return 1 * factorial( 1 - 1);
    ↙ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ↙
if( 0 > 0){ 
}else {
    return 1; <- 1 을 리턴하게 된다.
}

return 된 1은 factorial( 1 - 1 )을 결과로 출력된다

결과적으로

return 1 * 1 -> return 2 * 1 * 1 -> return 3 * 2 * 1 * 1 로 출력되어

3! 인 3 * 2 * 1 = 6이 된다.

 

DFS를 구현할 때 기본적으로 Stack을 사용하는데 재귀를 이용해서도 구현할 수 있다.

---

참조

Do it! 자료구조와 함께 배우는 알고리즘 입문

재귀