[알고리즘] 재귀함수, 재귀 알고리즘 (Recursion Function)

코딩테스트를 진행하다보면, 재귀함수(재귀알고리즘)을 사용하게되곤 해서 한번쯤 정리가 필요하겠다 싶은 마음이 들었다.

 

 

일단 재귀함수란,

간단히 말하면 자신을 계속해서 호출하는 함수 이다.

 

같은 코드를 반복해서 사용해야할 때에, 유용하게 사용된다.

보다 간단하게 문제를 해결해나갈 수 있게 된다.

 

 

유의해야할 점은

Break Point를 잘 만들어야 한다는 것이다.

 

계속해서 반복호출하다보면 스택오버플로우(Stack Overflow) 오류가 발생할 수 있다.

용량은 한정되어있는데, 계속해서 호출하고 리턴하지 않으니 용량을 많이 차지하고 그러다보니 일어나는 것이라고 생각하면 되겠다.

( 사탕을 비닐에 넣는데, 계속해서 사탕을 넣기만하면 비닐이 터져버리는 것과 같다고 생각하면 된다. )

 

 

주로 사용되는 때는

 

- 구구단

- 1 ~ N까지의 합계 구하기

- 피보나치 수열 구하기

 

 

등인데, 코딩테스트 때에 찾아보면 생각보다 많이 쓰이고 있음을 알 수 있다.

 

 

나는 이럴 때에 사용한다.

 

1. 코드가 반복적으로 사용된다.

2. break point가 명확하다.

3. 분기점이 명확하다.

 

세 가지 조건을 충족하면 망설임없이 사용하곤 했다.

 

분기점이 명확하다함은 분기점이 있을 때의 이야기지만,

어떠한 기준이 되는 데이터가 두 가지의 경우로 나뉜다던가 하는 것을 말한다.

 

예를 들면, 1부터 N까지 데이터를 조작하여 홀수인 경우에는 값을 더하고 짝수인 경우에는 값을 곱한다.

혹은, 1부터 N까지 데이터를 X라는 데이터와의 차를 이용해서 음수의 경우에는 A작업, 양수의 경우에는 B작업을 한다.

 

이렇게 되면 N 또는 1이 break point가 되는 것이다.

 

 

한 가지 예시 코드를 주자면, sum이라는 전역변수를 통해 1부터 N까지의 합계를 구하는 코드를 간단하게 짜보았다.

int sum = 0;

public static void main(String args[]){
	plus_data(10);
}

public void plus_data(int num) {
	if(num == 1) { 		// break point, 1이되면 재귀함수 호출을 멈춘다.
    	System.out.println("합계 : " + sum);
        return;
    }
    
    sum += num;
    plus_data(num-1);

}