재귀적 사고방식 기르기

여러 재귀 문제에는 다양한 “카테고리”가 있다. 어떤 카테고리에 효과적인 기법을 터득하면 같으 카테고리에 속하는 문제와 마주했을 때 같은 기법을 적용할 수 있다.

재귀가 유용하게 쓰이는 영역

• 임의의 단계만큼 깊이 들어가는 문제를 풀 때
• 하위 문제의 계산 결과에 기반해 계산할 수 있을 때

재귀 카테고리 1

• 반복적으로 한 작업을 실행하는 알고리즘

1. 카운트다운

// 재귀
function countdown(number){
	console.log(i);
	if(number === 0) return;
	countdown(number - 1);
}
countdown(10);

함수의 출력 횟수는 매번 다르나 코드의 본질은 결국 하나의 작업, 즉 숫자 출력 작업을 반복적으로 실행하는 것!

2. 숫자 배열을 받아 배열 내 각 숫자를 2배로 만드는 알고리즘

새배열 x, 기존 배열 수정

[1,2,3,4,5] ⇒ [2,4,6,8,10] (배열 내 값을 2배로 만드는 과정)

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

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

하지만 재귀함수에 인수는 배열 뿐이다. 인덱스를 기록하고 증가시킬 방법이 필요하다.

!!!_) 바로 인자를 하나 더 전달하는 것

함수 앞부분을 수정해 배열 외에 기록할 인덱스까지 인수로 받자. 그리고 연속적인 재귀호출마다 인덱스를 증가시킨다.

function double_array(array, index){
	array[index]*=2;
	double_array(array, index+1);
}

연속된 호출마다 첫 번째 인수로 배열을 다시 전달하고 증가된 인덱스도 함께 전달한다. 이로써 전형적인 루프처럼 인덱스를 기록할 수 있다.

⇒ 여기에 이제 추가적으로 기저 조건까지 넣으면 끝이 난다.

function double_array(array, index = 0){
	if(index>array.length) return; // 기저조건
	array[index]*=2;
	double_array(array, index+1);
}

double_array([1,2,3,4,5])

꿀팁!

원래는 함수를 호출할 때, double_array([1,2,3,4,5],0) 이렇게 초기 index 값으로 0을 넣어줘야했지만, 깔끔하지 못하므로, 함수 파라미터에 index=0 이라고 인수 기본 값을 할당한다. 이렇게 하면 함수를 처음 호출할 때, 인덱스 인자를 전달하지 않아도 된다!

🔥제자리 수정 (in-place)
데이터를 조작하는 방법 2가지
ex) [1,2,3,4,5] ⇒ [2,4,6,8,10] (배열 내 값을 2배로 만드는 과정)
1. 원래 배열은 그대로 두고, 2배로 만든 데이터를 포함하는 새 배열을 생성

a= [1,2,3,4,5]
b= double_array(a)
console.log(a) // [1,2,3,4,5]
console.log(b) // [2,4,6,8,10] 
//원래 배열을 바뀌지 않았고 b에는 새 배열이 들어있다.

2. 제자리(in-place) 수정 (실제 함수에 전달된 원본 배열을 바꾼다는 뜻)

console.log(a) // [2,4,6,8,10] 
console.log(b) // [2,4,6,8,10] 

제자리 함수는 실제로 a를 수정했고 b는 사실 상 a와 같은 배열을 가리킬 뿐이다.
cf. 새 배열을 생성하든 원래 배열을 제자리에서 수정하든 선택은 사용자의 몫이고 프로젝트 상황에 따라 달라진다!!

---

재귀 카테고리 2

• 하위 문제에 기반해 계산 수행하기 알고리즘

1. 계승 문제

6x5x4x3x2x1 을 어떻게 풀어나갈 것인가?

• 루프문 (상향식)

function factorial(number){
	product = 1;
	
	while(1<number){
		product *= number;
		number-=1;
	}
	return product;
}

• 하위 문제에 기반해 계승을 계산하기 (하향식)

factorial(6) = 6x5x4x3x2x1

factorial(5) = 5x4x3x2x1

factorial(6) = 6 x factorial(5)

즉, factorial(5)의 결과를 알면 간단히 그 결과에 6을 곱해 factorial(6)의 답을 구할 수 있다. factorial(5)는 더 큰 문제의 결과를 계산하는 데 쓰이는 더 작은 문제이므로 factorial(5)를 factorial(6)의 하위문제라고 부른다.

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

return number * factorial(number - 1); 이게 핵심 코드이다!!

상향식 vs 하향식

위에서 전형적인 루프로 상향식 방식을 풀어 보았으나 재귀로도 상향식 전략을 구할 수 있다.

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

이렇게 재귀로 상향식 방식을 구현할 수 있으나, 그다지 간결하지 못하며, 전형적인 루프에 비해 장점이 없다.

상향식에서는 루프를 쓰든 재귀를 쓰든 같은 전략으로 계산한다.

하지만, 하향식에서는 무조건 재귀를 써야한다. 하향식 전략을 구현할 방법은 재귀뿐이다.

---

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

재귀는 하향식 방식을 구현하는 데 탁월하다. 하향식 사고방식은 문제를 해결하는 새로운 사고 전략을 제공한다.

하향식으로 풀어나갈 때 → “문제를 뒤로 미룬다.”

return number * factorial(number - 1); 이 코드를 예시로 보면, factorial 함수가 어떻게 동작하는지 알아야할까? → 몰라도 된다. 다른 함수를 호출하는 코드를 작성할때는 내부적으로 어떻게 동작하는지 모르더라도 늘 그 함수가 올바른 값을 반환하리라고 가정한다.

즉, 세부사항은 하위 문제에서 다루게 두자! 라는 전략이다.

🔥 하향식 사고 절차
1. 작성 중인 함수를 이미 누군가 구현해 놓았다고 상상하자.
2. 문제의 하위 문제를 찾자.
3. 하위 문제에 함수를 호출하면 어떻게 되는지 보고 거기서부터 시작하자.

---

하향식 재귀 예시

• 배열 합

주어진 배열의 모든 수의 합 ex) [1,2,3,4,5] ⇒ 15 return

가정 : sum 함수가 이미 구현되어 있다고 생각하자! (뻔뻔)

순서 - 1 하위 문제 찾기
sum 함수 잘 동작 → sum([2,3,4,5]) ⇒ 14 잘 나오겠지~
그럼 index 첫번째 값만 따로 더 해주면 끝나네~

순서 - 2 이런식으로 동작한다고 가정하고 코드 작성
return array[0] + sum(array.slice(1))

순서 - 3 코드 완성!
sum이 어떻게 동작해야하는지 생각을 안했다.

function sum(array){
	return array[0] + sum(array.slice(1));
}

순서 - 4 기저조건 추가

function sum(array){
	if(array.length ===1) return array[0];
	return array[0] + sum(array.slice(1));
}

---

• 문자열 뒤집기

abcde → edcba

가정 : revese 함수 잘되어 있다고 가정

순서 - 1 하위 단계 생각 →reverse(bcde) 만 보낸다.
array[0] 값을 맨 뒤에 배치한다.

순서 - 2
return reverse(array[1,array.length-1]) + array[0]

순서 - 3 + 기저 조건 추가

function reverse(array){
	if(array.length === 1) return array[0];
	return reverse(if (string[0]===’x’){

return 1 + count_x(array.slice(1)) + array[0]; 
}

---

• x 개수 세기

axbxcxd → x갯수 return 3
가정 : count_x 함수가 잘 동작한다고 생각

순서 - 1 count_x 의 하위를 생각하자. index 하나 꺼내서 그게 x인지 아닌지

순서 - 2

if (string[0]===’x’){

return 1 + count_x(string.slice(1)) // string[1:] 과 동일

}else{

return count_x(string.slice(1))

}

순서 - 3 + 기저조건

function count_x(string){
	if(string.length === 1){
		if(string[0]==='x') {
			return 1
		}
		else{ 
			return 0
		}
	}

	if (string[0]===’x’){
		return 1 + count_x(string.slice(1))
	}else{
		return count_x(string.slice(1))
	}
}

• 기저조건 단순화

	// 변경전
	if(string.length === 1){
		if(string[0]==='x') {
			return 1
		}
		else{ 
			return 0
		}
	}

---

//변경 후
	if(string.length === 0){
			return 0;		
	}

---

재귀의 의문 ⇒ 계단 문제

새로운 사고 전략을 사용해 하향식 재귀로 특정 계산 문제를 해결하는 법을 배웠다. 하지만 여전히 회의적이고 의문이 들 수 있다. “대체 이 새로운 사고 전략이 왜 필요한가?? 루프만으로도 문제를 잘 풀어왔는데.”

⇒ 간단한 계산에는 루프가 더 나을 수도 있지만, 복잡한 함수라면 재귀적인 사고 방식으로 코드를 훨씬 쉽게 작성할 수 있다. 그 예시가 아래 계단 문제이다.

• 계단 문제

문제 : N개 짜리 계단이 있고 누군가 한 번에 하나 혹은 둘, 세 계단까지 올라갈 수 있다고 하자. 계단 끝까지 올라가는 경로는 몇개일까?

😎 상향식 사고

계단 수	1	2	3	4	5	6	11
경로	1	2	4	7	?	??	??????

계단 수가 많아질수록 조합이 늘어나므로, 복잡해진다.

---

😎 하향식 사고

11개짜리 계단이라고 가정

1번째 하위문제는 → 10계단

1. 우선 11개짜리 계단에 오르려면 적어도 10개짜리 계단에 오르는 단계 수만큼은 무조건 필요하다. (즉, 10계단까지의 경로를 알고, 거기에 + 1계단만 하면 되니까!)
2. 그리고 추가로 9번째 계단에서도 11번쨰 계단으로 바로 이동이 가능하다. (2칸씩 이동도 가능하니까)
   (또한, 잘 생각해보면 10번째 계단에서 11번째 계단으로 가는 경로를 따를 경우, 9번째 계단에서 11번째 계단으로 가는 경로는 따르지 않을 것이다. 반대로 9번째 계단에서 11번째 계단으로 바로 가면 10번째 계단을 거치는 경로는 따르지 않을 것이다.)
3. 근데 여기서 추가로 8번째 계단에서 11번째 계단으로 갈 수 있다 (3칸씩,,ㄷㄷ)
4. 결론 : 10번째 계단까지 가는 경로 + 9번째 계단까지 가는 경로 + 8번째 계단까지 가는 경로 === 11번째 계단까지 가는 경로

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

*기저조건 찾기

number_of_paths(0) === 0 이 나와야한다.

number_of_paths(1) === 1 이 나와야한다.

number_of_paths(2) === 2 이 나와야한다.

number_of_paths(3) === 4 이 나와야한다.

이것들을 기저조건에 하드코딩 할 수 있다. 하지만 깔끔하지 않다. 다시 생각해보면

number_of_paths(3)=number_of_paths(2) + number_of_paths(1) + number_of_paths(0)

number_of_paths(2)=number_of_paths(1) + number_of_paths(0) + number_of_paths(-1)

number_of_paths(1)=number_of_paths(0) + number_of_paths(-1) + number_of_paths(-2)

number_of_paths(0) 이 값이 1만 나오면 된다!!

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

---

• 애너그램

문자열 내 모든 문자들을 재배열한 문자열이다.!

ex) “abc” ⇒ [abc, acb, bac, bca, cab, cba]

function anagramsOf(string) {
  // 기저 조건: 문자열이 한 글자인 경우 그대로 반환
  if (string.length === 1) {
    return [string];
  }

  // 애너그램 결과를 저장할 배열
  const collection = [];

  // 두 번째 문자부터 마지막 문자까지 부분 문자열의 애너그램을 생성
  const substringAnagrams = anagramsOf(string.slice(1)); // string[1:]와 동일

  // 각 부분 문자열의 애너그램을 순회
  substringAnagrams.forEach((substringAnagram) => {
    // 삽입 가능한 모든 위치에 현재 문자(string[0])를 삽입
    for (let index = 0; index <= substringAnagram.length; index++) {
      // 부분 문자열 애너그램의 복사본을 생성
      const copy = substringAnagram.split(""); // 문자열을 배열로 변환
      copy.splice(index, 0, string[0]); // 현재 문자(string[0])를 삽입
      collection.push(copy.join("")); // 배열을 문자열로 변환하여 결과에 추가
    }
  });

  // 전체 애너그램 컬렉션 반환
  return collection;
}

// 테스트 실행
const result = anagramsOf("abcd");
console.log(result);
// result 값 : [  'abcd', 'bacd', 'bcad', 'bcda',  'acbd', 'cabd', 'cbad', 'cbda',  'acdb', 'cadb', 'cdab', 'cdba',  'abdc', 'badc', 'bdac', 'bdca',  'adbc', 'dabc', 'dbac', 'dbca',  'adcb', 'dacb', 'dcab', 'dcba']

코드 설명

1. 기저 조건:
   • 문자열이 한 글자인 경우에는 애너그램이 자신이므로 배열에 담아 반환:

     javascript
     코드 복사
     if (string.length === 1) {
       return [string];
     }
     

2. 부분 문자열의 애너그램 생성:
   • string.slice(1)을 사용해 첫 번째 문자를 제외한 나머지 문자열로 재귀 호출:

     javascript
     코드 복사
     const substringAnagrams = anagramsOf(string.slice(1));
     

3. 현재 문자 삽입:
   • substringAnagrams 배열의 각 문자열에 대해 삽입 가능한 모든 위치에 첫 번째 문자(string[0])를 삽입.
   • copy.splice(index, 0, string[0])로 현재 문자를 삽입한 후 결과 배열에 추가:

     javascript
     코드 복사
     for (let index = 0; index <= substringAnagram.length; index++) {
       const copy = substringAnagram.split("");
       copy.splice(index, 0, string[0]);
       collection.push(copy.join(""));
     }
     

4. 최종 결과 반환:
   • 재귀적으로 생성된 모든 애너그램을 포함한 배열을 반환:

     javascript
     코드 복사
     return collection;
     

---

애너그램의 효율성

길이가 n인 문자열은 애너그램을 N! 생성한다. 즉, 빅요 표기법으로는 O(N!)으로 나타낸다. 이를 계승시간이라고도 한다. O(N!)은 매우 느리지만, 모든 애너그램을 생성해야하는데 문자 N개로 된 단어에는 애너그램이 N!개이니, 더 나은 방법이 없다,

마무리

재귀는 다양한 문제를 해결하는 훌륭한 도구이지만 주의 깊게 사용하지 않으면 코드가 현저히 느리다. 다음 포스팅에서는 재귀를 사용하되, 코드를 깔끔하고 빠르게 유지 시키는 법을 적어보겠다.

연습문제

1. 문자열 배열을 받아 모든 문자열에 쓰인 문자 개수를 반환하는 함수를 재귀적으로 작성

[”ab”, ”c”, ”def”, “ghij”]

function returnString(array){
	if(array.length === 0) return 0;
	return array[0].length+returnString(array.slice(1));
}

1. 수 배열을 받아 짝수만 포함하는 새 배열을 반환하는 함수

function returnOdd(array, newArray=[]){
	if(array[0]%2===0)newArray.push(array[0]);
	return returnOdd(array.slice(1),newArray);
}

// 다른 풀이

function returnOdd(array){
	if(array[0]%2===0)return [array[0]] + returnOdd(array.slice(1));
	else returnOdd(array.slice(1));
}

1. 삼각수 배열. 1,3,6,10,15,21 (n번째값은 n에 바로 앞 숫자를 더한 값이다) ex) 7→앞숫자21 ⇒28

function 삼각수(n){
	if(n===1) return 1;
	return n + 삼각수(n-1);
}

1. 문자열을 받아 문자 ‘x’ 가 들어간 첫 번째 인덱스를 반환하는 함수를 재귀적으로 작성하라. (무조건 문자열의 하나 이상의 x가 있다고 가정)

function findX(string, n=0){
	if(string[n]==='x') return n;
	return findX(string.slice(1),n++);
}

// 다른 풀이

function findX(string){
	if(string[0]==='x') return 0;
	return findX(string.slice(1))+1;
}

1. 유일경로 라고 불리는 문제. 행과 열로 이루어진 격자판 존재. 행 수와 열 수를 받아 왼쪽 맨 윗칸에서 오른쪽 맨 아랫칸까지 가는 최단 경로의 개수를 계산하는 함수 작성

   ex) 3개 행과 7개 열로 이뤄진 격자판은 다음과 같다. s → f (무조건 오른쪽이동, 아래이동) 2개 선택지밖에 없음)

   S
   						F

function onlyDestination(row,col){
	if(row===1 || col===1) return 1;
	return onlyDestination(row,col-1) + onlyDestination(row-1,col);

}

2x2 → 2

3x2 → 3

3x3 → 6

🔥해설
이동할 방법은 둘뿐 (한칸 오른쪽, 한칸 아래쪽)
고유한 최단 경로의 총수는 s의 오른쪽 칸에서 가는 경로 수와 s의 아래쪽 칸에서 가는 경로수의 합
→ 2행 2열이라고 치면 갈 수 있는 법은 2개인데,
시작점에서 오른쪽으로 이동했다고 치고, 끝점까지 가는 법 1가지
시작점에서 아래쪽으로 이동했다고 치고, 끝점까지 가는 법 1가지 +) 그래서 2가지이다.!
결국) 기저조건은 1행1열일때, 이다.!