[Algorithm] 재귀 알고리즘이란 recursion algorithm

what is recursive algorithm?

How can I solve recursion algorithm?

 

 

 

 

재귀 알고리즘

 

알고리즘에는 여러가지 방법이 존재한다. 그 중에서도 분할 정복법의 한 유형인 재귀 알고리즘은 문제를 더 작은 구조의 문제로 잘게 쪼개면서 연산을 분산시키는 방식이다. 

만약 자연수로 구성된 배열의 총 합을 구하는 문제가 주어진다면 배열 전체를 더하기 보다는 배열을 잘게 쪼개는 방식으로 총합을 구할 수 있다.

const arr = [1,2,3,4,5];

 

첫번째 연산은 1과 [2,3,4,5]로 분리한다. 

1 + [2,3,4,5]
1 + 2 + [3,4,5]
1 + 2 + 3 + [4,5]
1 + 2 + 3 + 4 + [5];

 

더 이상 문제가 쪼개지지 않을 때 까지 함수 자신을 호출하는 과정을 반복한 후 최종값을 반환하게 된다.

 

예제 문제

문제 : 자연수의 합으로 이뤄진 배열의 총 합을 구하시오. 

풀이 : 

입력값은 배열로 받는다.

탈출조건은 배열의 총 길이가 0보다 작아지는 경우다.

재귀로직은 현재 배열의 가장 마지막 요소와 배열의 길이를 1씩 줄이면서 함수 자신을 호출한다.

function arrSum(arr) {
    // TODO: 여기에 코드를 작성합니다.
  
  	// 탈출 조건
    if(arr.length<=0) return 0;
    
    // 재귀 (함수 자신을 호출)
    return arr[arr.length-1] + arrSum(arr.slice(0,arr.length-1));
  }

console.log(arrSum([1,2,3,4,5]));

최종적으로 아래 그림과 같이 연산이 진행된다.

1 + [2,3,4,5]
1 + 2 + [3,4,5]
1 + 2 + 3 + [4,5]
1 + 2 + 3 + 4 + [5];

 

 

재귀 알고리즘은 언제 사용하면 좋을까?

 

재귀 알고리즘(Recursion Algorithm)은 문제를 더 작은 문제로 분해할 수 있는 경우나, 반복문의 중첩이 많아서 결과를 예측하기 힘든 경우 유용한 알고리즘이다. 

모든 재귀 알고리즘은 for, while과 같은 반복문으로 표현할 수 있다. 이 때 반복문이 코드의 가독성을 해칠 때 재귀 알고리즘은 가독성과 유지보수성을 향상시키게 된다. 

재귀 알고리즘의 대표적인 예로는 하노이의 탑 문제와 조합(Combination) 문제가 있다. 

 

재귀 알고리즘 사용하기

 

① 문제를 단순화 시키기

재귀 알고리즘을 사용하는 가장 첫번째 순서는 문제를 단순화 시키는 것이다. 입력갑과 출력값을 정의하는 것으로 시작한다. 

② 더 작은 문제로 분해하기

입력값과 출력값이 정해졌다면 문제를 더 작은 문제로 쪼개는 작업을 거친다. 통상 입력값을 기준으로 더 이상 쪼갤 수 없는 단계 까지 문제를 분해한다. 입력값을 통해 문제의 순서와 크기를 쪼개나간다. 

모든 재귀 알고리즘은 for문과 while문으로 구성할 수 있다는 사실을 잊지 말자. 즉, 반복문에서 중요한 변수는 반복문 내에서 증감하는 입력값이다. 재귀 알고리즘을 구성할 때 가장 중요한 변수가 되는 것도 입력값이 된다. 

위의 예제에서 배열을 입력받아 총 합을 구하는 문제의 경우 5개의 배열 인자를 4개, 3개, 2개, 1개로 쪼개고 1개의 인자를 가진 배열은 더 이상 쪼갤 수 없기 때문에 출력 로직을 구성한다.

③ 가장 단순한 문제(base case)를 해결

문제를 쪼갰다면 이제는 재귀 알고리즘에서 가장 단순한 문제를 해결한다. 재귀의 기초(base case)는 탈출 조건에서 위치한다. 위의 예제에서는 [1] 1개의 배열 인자를 가진 배열을 가지게 되는 단계에서 재귀의 기초를 구성한다.

④ 문제 해결 완료

재귀의 기초가 완성되었다면 분해했던 문제를 하나씩 조립하면서 재귀 로직을 완성한다. 

 

일반적인 재귀 알고리즘

function recursion(input){
	// Base Case
    // 문제를 더 이상 쪼갤 수 없는 단계
    // a.k.a 탈출 조건
    if(문제를 더 이상 분해할 수 없는 단계){
    	return 가장 단순한 문제의 결과
	}
    
    // Recursion Case
    // 작은 문제를 조합한 형태
    return 작은 문제의 해를 사용하여 복잡한 문제를 해결
}