[알고리즘과 자료구조] 재귀함수를 사용해 다양한 문제를 접근해보자

📝 '누구나 자료구조와 알고리즘' 책을 공부한 내용을 담고 있습니다.

11장 재귀적으로 작성하는 법

11장에서는 재귀적 사고방식을 기르는 데 집중한다.

11.1 재귀 카테고리: 반복 실행

여러 가지 재귀 문제를 다루면서 문제에 다양한 "카테고리"가 있음을 알게 됐다. 같은 카테고리에 속한 문제는 같은 기법으로 해결할 수 있다.

예를 들어, 반복적으로 한 작업을 실행하는 알고리즘이 있다. 우주선 카운트 다운 알고리즘이 대표적이다. 10에서부터 0까지의 수를 반복적으로 출력한다.

function countdown(number) {
	console.log(number);
    
    if (number === 0) { // number가 0일 때가 기저조건
    	return;
    } else {
    	countdown(number -1)
    }
}

else 구문에서 재귀 함수를 다시 한 번 호출하여 반복적으로 숫자를 출력한다.

11.1.1 재귀 트릭: 추가 인자 넘기기

반복 실행 알고리즘 예시 중 숫자 배열을 받아 배열 내 각 숫자를 두 배로 만드는 알고리즘을 작성하려고 한다. 단 새 배열을 만드는 것이 아니라 배열 자체에서 수정한다.

만약 재귀 대신 루프를 사용한다면, 인덱스를 기록하는 변수를 두고 다음 코드처럼 계속해서 1씩 증가시켜야 한다.

function double_array(array){
  let index = 0;
  
  while (index < array.length) {
  	array[index] *=2;
    index += 1;
  }
}

재귀 함수를 사용한다면 어떻게 해결할까?

index를 인수를 받아서 index가 array.length보다 작을 때까지 재귀 함수를 호출한다. index를 대신 0을 긴본값으로 받아서 사용할 수도 있다. 이렇게 함수 인자를 추가해서 재귀 함수로 문제를 해결할 수 있다.

function double_array(array, index){
  if (index >= array.length) return;
  
  array[index] *= 2;
  double_array(array, index + 1);
}

[참고] 제자리 수정(in-place)
배열 데이터를 조작하는 2가지 방법이 있다.
첫 번째, 원래 배열은 그대로 두고 새 배열을 생성하는 방법이다.
두 번째, 제자리 수정 방법으로, 원본 배열을 바꾸는 것이다.
어떤 방법을 선택하든 사용자의 몫이고, 프로젝트 상황에 따라 달라진다.

11.2 재귀 카테고리: 계산

재귀가 유용하게 쓰이는 영역은 하위 문제의 계산에 기반해 계산할 수 있을 때다.

예를 들어, 6의 계승(factorial) 문제가 있다.

6 * 5 * 4 * 3 * 2 * 1

어떤 수의 계승을 계산하는 함수를 작성할 때 1부터 시작해 결과를 계산해 나가는 루프를 사용해도 된다. 즉, 1에 2를 곱하고, 그 결과에 3을 곱하고, 다시 4를 곱해서 6까지 가는 방식이다.

function factorial (number) {
	let product = 1;
  
  for (let i = 1; i <= number; i++) {
  	product *= i
  }
  
  retrun product;
}

하지만, 문제에 다르게 접근해 볼 수 있다. 즉, 하위 문제에 기반해 계승을 계산하는 것이다.

하위 문제(subproblem)의 관점에서 factorial(6)은 factorial(5)의 결과에 6을 곱한 값이다. 즉, factorial(6) = 6 * factorial(5) 이다. 코드로 구현하면 다음과 같다.

function factorial (number) {
	if (number === 1) {
      return 1;
    } else {
      return number * factorial(number - 1)
    }
}

두 가지 계산 방식

재귀 함수를 사용해서 "상향식" 또는 " 하향식"으로 문제를 해결할 수 있다.
단, 재귀로 상향식 전략을 구현할 때, 인자를 추가로 전달해야 한다.

factorial 문제를 상향식으로 풀어보면

function factorial (number, i = 1, product = 1) {
	if ( i > number ) return product;
  	return factorial(number, i + 1, product * i)
}

이 함수의 인자는 3개이다. 하나는 계승 수인 number, 두 번째는 1부터 시작해 매 호출마다 1씩 증가하는 변수 i, 마지막으로 i와 계속 곱한 결과를 저장하는 변수 product이다.

재귀 함수를 상향식으로 쓸 수 있지만, 루프를 사용하는 것보다 낫다고 볼 수 없다. 상향식에서는 재귀나 루프나 동일한 방식이다.

하지만, 하향식에서는 재귀를 써야한다.

11.3 하향식 재귀: 새로운 사고방식

재귀는 하향식 방식을 구현하는 데 탁월하다. 재귀적 하향식 방식은 문제를 완전히 다른 방식으로 생각하게 해준다.

11.4 계단 문제

n개의 계단을 올라는 경로 문제를 풀어보자.

계단 수가 1개일 때, 가능한 경로는 1개이다.

계단 수가 3개면 가능한 경로는 4개이다.

1,1,1
1,2
3

계단 수가 4개면, 가능한 경로는 7개이다.
1,1,1,1
1,1,2
1,2,1
1,3
2,1,1
2,2
3,1

그렇다면, 모든 경로를 계산하는 코드를 어떻게 작성할까?

"하향식"으로 생각하면 문제가 단순해진다.
11개 계단의 경로를 구할 때 10개 계단 경로를 알면 된다. 10번째 계단까지 가는 경로 수에 9번째 계단까지 경로 수를 더한 값이다. 따라서 N개 계단일 때 경로 수는 다음과 같다.

number_of_paths(n-1) + number_of_paths(n-2) + number_of_paths(n-3)

계단 문제 기저 조건

계단 문제의 기저 조건은 알아내기 까다롭다. n이 0보다 작으면 0이고, n이 1이거나 0이면 1이 된다. 이 기저조건을 추가한 코드는 다음과 같다.

function number_of_paths(n){
	if (n < 0) return 0;
  	if (n === 1 || n === 0) return 1;
  	return number_of_paths(n-1) + number_of_paths(n-2) +number_of_paths(n-3)
}

11.5 애너그램 생성

가장 복잡한 재귀 문제인 주어진 문자열의 모든 애너그램(anagram) 배열을 반환하는 함수를 풀어본다.

애너그램(angram)
문자열 내 모든 문자들을 재배열한 문자열

문자열 "abcd"의 모든 애너그램을 구해보자. "abcd"의 하위 문제는 "abc"일 것이다. "abc"의 모든 애너그램을 반환하는 애너그램 함수가 있을 때, 이를 사용해서 어떻게 "abcd"의 모든 애너그램을 만들어낼까?

"abc"으로 가능한 문자열은 다음과 같다.

"abc"
"acb"
"bac"
"bca"
"cab"
"cba"

각 문자열의 알파벳 앞뒤에 d를 넣으면, "abcd"의 애너그램을 만들 수 있다.

자바스크립트 코드를 구현

function anagrams (string) {
    //string이 1개일 때
	if (string.length === 1) return [string];
  
   // 모든 애너그램 저장할 배열 
    let collection = []
    
   // 두 번째 문자부터 마지막 문자까지의 부분 문자열에서 모든 애너그램을 찾는다.
   // 예를 들어, string이 "abcd"면 부분 문자열 "bcd"이니
   // "bcd"의 모든 애너그램을 찾는다.
   let substring_anatrams = anagrams();
   
   // 각 부분 문자열을 순회한다.
  
  // 0부터 string 끝을 하나 지난 인덱스까지
  //부분 문자열의 각 인덱스를 순회한다.
  
  // 부분 문자열 애너그램의 복사본을 생성한다. 
}