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

Deah (김준희)·2024년 3월 14일

개발서적 알고리즘 자료구조

누구나 자료구조와 알고리즘 (개정2판)

목록 보기

11/15

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

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

"반복적으로 실행하는" 카테고리 유형에 접근해보자.

숫자 배열을 받아 배열 내 각 숫자를 두 배로 만드는 알고리즘을 작성하려고 한다.
단 새로운 배열을 만드는 것이 아닌 기존 배열을 수정해야 한다.

이 알고리즘도 '반복 실행'을 한다. 정확하게는 '반복적으로 숫자를 두 배로 만든다' 라고 할 수 있다.

제자리 수정(in-place)이란?
자료 구조를 추가로 사용하지 않고 입력을 변환하는 알고리즘.
그러나 추가적인 변수를 위해 약간의 추가 저장 공간은 허용된다.

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

테스트

let arr = [1, 2, 3, 4];
let idx = 0;

doubleArray(arr, idx);

console.log(arr);   // [2, 4, 6, 8]

11.2 재귀 카테고리: 계산

앞에서는 반복 실행 작업에서 재귀를 이야기 했다.
지금부터는 일반적인 카테고리인 하위 문제에 기반해 계산 수행하기를 알아보자.

두 수의 합을 반환하는 함수나, 배열에서 최댓값을 찾는 함수처럼 계산 수행이 목적인 함수가 많다.
그리고 이런 함수는 입력에 따른 계산 결과를 반환한다.

10장. 재귀를 사용한 재귀적 반복에서 한 가지 영역이 임의의 단계 만큼 깊이 들어가는 문제를 풀 때 재귀가 유용하게 쓰인다고 했다. 그리고 또 하나는 하위 문제 계산 결과에 기반해 계산할 수 있을 때다.

하위문제(Subproblem)란?
똑같은 문제에서 입력을 더 작게한 문제
어느 문제를 풀기 위해 문제를 쪼개면 쪼개진 문제에서 다시 똑같은 문제를 풀어야 하는 경우에 해당한다.

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

위 코드는 어떤 수의 계승을 계산하는 함수이다.
1부터 시작해 자기 자신까지 곱해가며 전형적인 루프를 사용한 예이다.

🤓 하지만 다르게 접근해하여 하위 문제에 기반해 계산해본다면?

하위 문제 관점에서 factorial(6)은 factorial(5)의 결과에 6을 곱한 값이다.

factorial(6) : $6 * 5* 4 * 3 * 2 * 1$
factorial(5) : $5* 4 * 3 * 2 * 1$

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

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

두 가지 계산 방식

앞서 본 것 처럼 계산 함수를 작성하는 방식은 상향식과 하향식 두 가지이다.

상향식 (bottom up)
하향식 (top down)

🤔 루프를 통해 상향식 방식을 시도해보았으니 재귀로도 구현해볼까?

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

n : 계승 수
i : 1부터 시작해 호출마다 n이 될 때까지 증가하는 변수
answer : 연속적인 수를 곱한 결과를 저장하는 변수

하지만 간결하지 못하며 루프 방식에 비해 큰 장점을 가지지도 않는다.
상향식에서는 루프나 재귀나 같은 전략으로 계산한다.

하지만 하향식에서는 무조건 재귀를 사용해야 한다. 이것이 재귀가 강력한 도구가 된 이유 중 하나이다.

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

재귀는 하향식 방식을 구현하는 데 탁월하다.
하향식 사고방식은 문제를 해결하는 새로운 사고 전략(mental strategy)을 제공해주기 때문이다.

return number * factorial(number - 1)

위 코드는 하향식 계승 함수 구현의 핵심이다. factorial(number - 1)의 결과를 이용해 계산한다.
다른 함수를 호출하는 코드를 작성할 때는 내부적으로 어떻게 동작하는지 모르더라도 늘 그 함수가 올바른 값을 반환한다고 가정한다.

위 예제에서도 factorial 함수 호출 결과에 기반해 답을 계산할 때 factorial 함수가 어떻게 동작하는지는 몰라도 되며 그저 옳은 결과를 반환하리라고 기대할 수 있다. 즉 문제를 해결하는 법을 몰라도 문제를 풀 수 있다는 것이다.

하향식 사고 절차

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

배열 합

[1, 2, 3, 4, 5]

주어진 배열 내 모든 수를 합하는 함수를 작성한다고 했을 때,

가장 먼저 할 일은 함수가 이미 구현되어 있다고 가정하는 것이다.
물론 내가 함수를 작성해야 하지만! 이미 작성하였고 잘 동작한다고 상상하자.
두 번째로는 하위 문제를 찾자.
예제에서는 첫 번째 원소를 제외한 배열 내 모든 수, 즉 [2, 3, 4, 5]이다.
마지막으로 하위 문제에 함수를 적용하면 어떻게 되는지 보자.
$2 + 3 + 4 + 5$ 의 결과인 $14$ 가 나올 것이고, 원래 배열에 적용하려면 $14$ 에 $1$ 을 더하면 된다.

코드로 구현한다면

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

그러나 남은 한 단계가 있다. 기저 조건을 처리해야 한다.
하위 문제에서 반복적으로 다시 하위 문제를 호출하다 보면 결국 sum([5])의 하위 문제에 도달한다.
그러나 더 이상 원소가 존재하지 않는다.

function sum(array) {
  	if (array.length === 1) return array[0];   // 기저 조건! (배열에 원소가 하나 남았을 때)
	return array[0] * sum(array.slice(1));
}

위와 같이 if문을 통해 기저 조건을 걸어주면 된다.

문자열 뒤집기

abcde

주어진 문자열을 뒤집어 반환하는 함수를 작성해보자.

함수는 이미 작성했다고 가정하고,
하위 문제를 찾자. 예제에서는 "bcde" 이다.
하위 문제에서 함수를 호출하자. "edcb" 라는 결과가 나올 것이고 그 끝에 a를 붙여주면 끝이다.

코드로 구현한다면

function reverse(string) {
	return reverse(string.slice(1)) + string[0];
}

이 문제에서 기저 조건은 문자열에 문자가 하나일 때이므로, 함수에 기저 조건을 추가하면 아래와 같다.

function reverse(string) {
  	if (string.length === 1) return string[0];   // 기저 조건!
	return reverse(string.slice(1)) + string[0];
}

X세기

axbxcxd

주어진 문자열에서 "x"의 개수를 반환하는 함수를 작성해보자.

함수는 이미 작성했다고 가정하고,
하위 문제 "xbxcxd" 이다.
하위 문제에 함수를 적용하면 결과값으로 3이 나오고,
여기에서 첫 번째 문자가 "x"인 경우와 아닌 경우를 분리하여 1을 더하거나 더하지 않으면 된다.

코드로 작성한다면

function countX(string) {
	if (string[0] === "x") {
    	return 1 + countX(string.slice(1));
    } else {
    	return countX(string.slice(1));
    }
}

다시 기저 조건을 처리할 차례이다.

이 문제에서 기저 조건은 문자열에 문자가 하나일 때지만,
그 문자열이 "x"일 수도 있고 아닐 수도 있으니 실제로는 2개의 기저 조건을 가진다.

function countX(string) {
  	if (string.length === 1) {
    	if (string[0] === "x") return 1;
      	else return 0;
    }
  
	if (string[0] === "x") {
    	return 1 + countX(string.slice(1));
    } else {
    	return countX(string.slice(1));
    }
}

🤯 코드가 너무 복잡해 보인다. 코드를 단순화 시켜보자!

function countX(string) {
	if (string.length === 0) return 0;
  
  	if (string[0] === "x") {
    	return 1 + countX(string.slice(1));
    } else {
    	return countX(string.slice(1));
    }
}

문자열의 길이가 1일 때 해당 문자가 "x"인지 아닌지를 구분했던 2개의 기저 조건에서
문자열이 비었을 때 0을 반환하는 1개의 기저 조건으로 단순화했다.
그리고 문자열이 하나 이상 일때, 첫 번째 문자열이 "x"이면 다음 호출 결과에 1을 더해준다.

11.4 계단 문제

🫠 반복 루프만으로도 잘 살아왔는데... 재귀라는 새로운 사고 전략이 왜 필요한가요?

간단한 계산에는 루프만으로 잘 해결할 수 있었다.
하지만 복잡한 계산이라면? 재귀를 통해 코드를 쉽게 작성할 수 있다.

만약 $N$ 개의 계단이 있고 누군가 한 번에 1개, 혹은 2~3개의 계단까지 올라갈 수 있다고 가정해보자.
계단의 끝까지 올라가는 경로는 과연 몇 개일까?

정답은 3개이다.

(1) 상향식 풀이 : 가장 단순한 경우부터 복잡한 경우로 거슬러 가는 법

1, 1
2

만약 계단 수가 2개면 경로는 2개이다. 한 계단씩 두 번 올라가거나 두 계단을 한 번에 올라갈 수 있다.

1, 1, 1
1, 2
2, 1
3

만약 계단 수가 3개면 경로는 4개다.

1, 1, 1, 1
1, 1, 2
1, 2, 1
1, 3
2, 1, 1
2, 2
3, 1

만약 계단 수가 4개면 경로는 7개다.

🤮 계단 수가 5개, 6개, 7개... 120,863개라면? 계산하기가 쉽지 않을 것이다.

(2) 하향식 풀이 : 단순해진 사고방식

11개짜리 계단이 있다고 했을 때, 이 문제에서 하위 문제는 계단이 10개인 경우이다.
10개짜리 계단에 오르는 경로 수를 알면 이를 기반으로 11개짜리 계단에 오르는 경로를 계산할 수 있다.

11개짜리 계단을 오르려면 적어도 10개짜리 계단을 오르는 단계 수 만큼은 필요하다.
즉 10번째 계단까지 오르는 모든 경로를 알면 거기서부터 꼭대기까지 한 계단 더 올라갈 수 있다.

그러나 이 계산이 완벽한 답을 계산해줄까?
9번째 계단에서 바로 11번째 계단으로 간다면? 10번째 계단은 오르지 않게 된다.

따라서 꼭대기까지 가는 경로 수는 최소 10번째 계단까지 가는 경로 수에 9번째 계단까지 가는 경로 수는 더한 값이다. 그리고 한 번에 3개의 계단을 오를 수 있으므로 8번째 계단에서 11번째 계단으로 바로 가는 경로 수도 포함해야 한다.

결론적으로 계단이 11개일 때, 8번째 계단과 9번째 계단과 10번째 계단까지 가는 모든 경로를 합해야 한다.

이 계산을 함수로 표현하면 다음과 같다.

function numberOfPaths(number) {
	return numberOfPaths(n - 1) + numberOfPaths(n - 2) + numberOfPaths(n - 3);
}

그리고 기저 조건을 추가해주면 된다.

계단 문제 기저 조건

이 함수에서 기저 조건을 알아내는 것은 까다롭다. 왜냐하면 $N$ 은 $3, 2, 1$ 중 하나일 수 있기 때문이다.
함수는 자기 자신을 0 또는 음수 $N$ 에 대해 호출하게 된다.

하드코딩 하는 방법

function numberOfPaths(number) {
	if (n <= 0) return 0;
  	if (n === 1) return 1;
  	if (n === 2) return 2;
  	if (n === 3) return 4;
  	return numberOfPaths(n - 1) + numberOfPaths(n - 2) + numberOfPaths(n - 3);
}

시스템을 조작할 기저 조건을 고안하는 방법

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

11.5 애너그램 생성

[
	"abc",
    "acb",
    "bac",
    "bac",
    "cab",
    "cba"
]

주어진 문자열의 모든 애너그램 배열을 반환하는 함수를 만들어보자.

애너그램(anagram)이란?
문자열 내 모든 문자들을 재배열한 문자열

코드로 구현한다면

기본 코드

function getAnagram(string) {
	if (string.length === 1) return string[0];
  
  	let collection = [];
  	let SUB_ANAGRAMS = getAnagram(string.substring(1));
  
  	for (let i = 0; i < SUB_ANAGRAMS.length; i++) {
      	let SUB_ANAGRAM = SUB_ANAGRAMS[i];
      
    	for (let j = 0; j < SUB_ANAGRAM.length; j++) {
        	let copy = SUB_ANAGRAM.slice(0);
          	collection.push(copy.slice(0, j) + string[0] + copy.slice(j));
        }
    }
  	
  	return collection;
}

해설

function getAnagram(string) {
  	// 기저 조건 : string의 길이가 1일 때, 해당 문자를 배열에 담아 리턴
	if (string.length === 1) return [string[0]];
  
  	// 애너그램을 저장할 배열 생성
  	let collection = [];
  	// 두 번째 문자부터 시작하는 문자열로 다시 애너그램 찾기
  	let SUB_ANAGRAMS = getAnagram(string.substring(1));
  
  	// 각 부분 문자열을 순회
  	for (let i = 0; i < SUB_ANAGRAMS.length; i++) {
      	let SUB_ANAGRAM = SUB_ANAGRAMS[i];
      
    	for (let j = 0; j < SUB_ANAGRAM.length; j++) {
        	let copy = SUB_ANAGRAM.slice(0);
          	collection.push(copy.slice(0, j) + string[0] + copy.slice(j));
        }
    }
  	// 배열에 담긴 애너그램 반환
  	return collection;
}

❗️ 책의 루비 예제 코드를 자바스크립트로 바꾸면서 뭔가 틀어진 거 같은데 이유를 모르겠다. 허허허허헣.

애너그램 생성의 효율성

애너그램 생성 알고리즘의 효율성을 분석해보자. 흥미로운 패턴을 발견할 수 있다.

문자 4개 : 애너그램 $4 * 3 * 2 * 1$ 개
문자 5개 : 애너그램 $5 * 4 * 3 * 2 * 1$ 개
문자 6개 : 애너그램 $6 * 5 * 4 * 3 * 2 * 1$ 개

바로 계승(factorial)의 패턴이다.

길이가 $N$ 인 문자열은 $N!$ 개의 애너그램을 생성한다. 빅 오로는 $O(N!)$ 으로 표기한다.
이 것을 계승 시간(factorial time)이라고도 부른다.

$O(N!)$ 은 매우 느리지만 모든 애너그램을 생성해야하기 때문에 더 나은 방법이 존재하지 않는다.
재귀는 위 알고리즘에서 중추적인 역할을 하며 복잡한 문제를 푸는 데 재귀가 어떻게 사용되는지 보여주는 중요한 예이다.

실습

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

["ab", "c", "def", "ghif"]

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

수 배열을 받아 짝수만 포함하는 새 배열을 반환하는 함수를 재귀적으로 작성하라.

[1, 2, 3, 4, 5]

function selectEven(arr) {
	if (arr.length === 0) return [];
  	if (arr[0] % 2 === 0) {
    	return [([0]].concat(selectEven(arr.slice(1));
    } else {
        return selectEven(arr.slice(1));
    }
}

삼각수()라는 수열이 있다. 1-3-6-10-15-21로 시작해 패턴 내 N번째 수까지 일정 패턴이 이어진다. N번째 값은 N에 바로 앞 숫자를 더한 값이다.예를 들어 수열에서 7번째 수는 7（즉 N）에 21（수열에서 바로 앞에 수）을 더한 28이다. 숫자 N을 받아 수열 내 올바른 값을 반환하는 함수를 작성하라. 즉 함수에 숫자 7을 전달하면 함수는 28을 반환해야 한다.

function triangle(n) {
	if (n === 1) return 1;
  	return n + triangle(n - 1);
}

문자열을 받아 문자 "x"가 들어간 첫 번째 인덱스를 반환하는 함수를 재귀적으로 작성하자.
단 문자열 내 무조건 "x"가 한 번 이상 나타난다고 가정하자.

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

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

function uniquePaths(rows, columns) {
	if (rows === 1 || columns === 1) return 1;
  	return uniquePaths(rows - 1, colums) + uniquePaths(rows, colums - 1);
}

요약

제자리 수정이란 자료 구조를 추가로 사용하지 않고 입력을 변환하는 알고리즘이며 재귀에서 많이 사용된다.
하향식 계산 방식에서는 무조건 재귀를 사용해야 한다.
하향식 사고 절차란 문제의 하위 문제를 찾아, 하위 문제에서 함수를 호출했을 경우를 생각하는 사고 방식이다.

Deah (김준희)

기록 중독 개발자의 기록하는 습관

이전 포스트

10장. 재귀를 사용한 재귀적 반복

다음 포스트

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

누구나 자료구조와 알고리즘 (개정2판)

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

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

테스트

11.2 재귀 카테고리: 계산

두 가지 계산 방식

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

하향식 사고 절차

배열 합

코드로 구현한다면

문자열 뒤집기

코드로 구현한다면

X세기

코드로 작성한다면

11.4 계단 문제

(1) 상향식 풀이 : 가장 단순한 경우부터 복잡한 경우로 거슬러 가는 법

(2) 하향식 풀이 : 단순해진 사고방식

계단 문제 기저 조건

11.5 애너그램 생성

코드로 구현한다면

기본 코드

해설

애너그램 생성의 효율성

실습

요약

10장. 재귀를 사용한 재귀적 반복

12장. 동적 프로그래밍

0개의 댓글