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

들어가기 전에

재귀(Recursion)란?
컴퓨터 과학에서 재귀는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며,
이를 프로그래밍에 적용하여 재귀호출(Recursive Call) 형태로 많이 사용된다.

재귀는 고급 알고리즘을 이해하기 위한 컴퓨터 과학의 핵심 개념이다.

function blah() {
	blah();
}

위 코드에서는 blah() 가 자기 자신을 무한대로 호출한다.
즉, 재귀는 함수가 자기 자신을 호출할 때 뜻하는 용어이다.

10.1 루프 대신 재귀

우주선 발사에 쓰일 카운트다운 함수를 프로그래밍 한다면
숫자를 받아 해당 숫자부터 0까지 표기해야 하며, 아래와 같이 코드를 작성할 수 있다.

• 반복 루프 사용

function countDown(number) {
	for (let i = number; i >= 0; i--) {
    	console.log(i);
    }
}

countDown(5);
// 5
// 4
// 3
// 2
// 1
// 0

• 재귀 사용

function countDow(number) {
	console.log(number);
  	countDown(number - 1);   // 함수 본인 호출! (재귀)
}

countDown(5);
// 5
// 4
// 3
// 2
// 1
// 0
.
.
.

처음 countDown(5) 를 호출하면 인수로 받은 number 은 5 부터 시작하여 콘솔에 5 를 출력하게 되고, number - 1 인 countDown(4) 를 호출한다.

countDown(4) 가 실행되어 콘솔에 4 를 출력하고, 다시 number - 1 이 되어 countDown(3) 을 호출한다.

이런식으로 루프없이 각 숫자를 콘솔에 출력하기 위해 재귀를 사용할 수 있다.
루프를 사용할 수 있는 경우라면 대부분 재귀도 사용할 수 있으며, 무조건 써야한다는 건 아니다.

10.2 기저 조건

그러나 위 countDown() 예제에서 number - 1 단계가 지속되면 콘솔에 음수가 출력되므로 완벽하지 않은 코드이다. 카운트다운을 0 에서 마치고 재귀가 지속되는 것을 막아야 한다.

function countDown(number) {
	console.log(number);
  
  	if (number === 0) return;
  	else countDown(number - 1);
}

조건문을 통해 number === 0 의 경우, 더이상 countDown() 을 호출하지 않도록 수정하여 문제를 해결할 수 있다.

이처럼 재귀에서 함수가 반복되지 않는 경우를 기저 조건(Base Case)이라고 부른다.
countDown() 예제에서는 0 이 기저조건이다.

모든 재귀 함수에서는 함수가 무한대로 호출되지 않도록 제어하는 기저 조건이 최소 1개 존재해야 한다.

10.3 재귀 코드 읽기

계승(factorial)이란?
무언가를 다른 존재로부터 물려받거나 혹은 이어받는다는 뜻으로,
수학에서 자연수의 계승은 그 수보다 작거나 같은 모든 양의 정수의 곱이다.

• 3의 계승 : $3 * 2 * 1 = 6$
• 5의 계승 : $5 * 4 * 3 * 2 * 1 = 120$

코드로 구현한다면

기본 코드

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

해설

function factorial(number) {
	if (number === 1) {  // 인자로 받은 number가 1일 경우 1을 리턴
    	return 1;
    } else { // 1이 아닌 수일 때, number을 -1씩 줄여가며 곱한 값을 리턴
    	return number * factorial(number - 1);
    }
}

여기서 if (number === 1) 은 factorial() 함수의 기저조건이다.

10.4 컴퓨터의 눈으로 바라본 재귀

재귀를 완벽히 이해하려면 컴퓨터가 재귀 함수를 어떻게 처리하는지 알아야 한다.

🥸 factorial(3) 을 예로 들어보자!

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

테스트

factorial(3);

factorial(3) {
	return 3 * factorial(2) {    // return 3 * 2 = 6
    	return 2 * factorial(1) // return 2 * 1 = 2
    }
}

위 코드는 엉망코드지만(?) 다음의 순서로 해석할 수 있다.

1. factorial(3)은 기저 조건에 해당되지 않으므로 else문을 실행하여 factorial(2)를 호출한다.
   (factorial(3)은 아직 진행 중...)
2. factorial(2)는 기저 조건에 해당되지 않으므로 else문을 실행하여 factorial(1)을 호출한다.
   (factorial(2)는 아직 진행 중...)
3. factorial(1)은 기저 조건에 해당되므로 1을 리턴하고, factorial(2)로 돌아간다.
4. factorial(2)에서 $2 * 1$ (= factorial(1)의 결과)의 결과인 $2$ 를 리턴하고, factorial(3)으로 돌아간다.
5. factorial(3)에서 $3 * 2$ (= factorial(2)의 결과)인 $6$ 을 리턴한다.

🧐 그렇다면 컴퓨터는 이러한 과정이나 정보들을 어떻게 기록할까?

호출 스택

컴퓨터는 이러한 과정을 스택을 사용하여 어떤 함수를 호출 중인지 기록한다.
이러한 스택을 호출 스택(call stack)이라고 부른다.

호출 스택(Call Stack)이란?
컴퓨터 프로그램에서 현재 실행 중인 서브루틴에 관한 정보를 저장하는 스택 자료구조
실행 스택, 제어 스택, 런 타임 스택 스택 혹은 기계 스택 이라고도 하며, 그냥 줄여서 스택이라고 부르기도 한다.

9장. 스택과 큐로 간결한 코드 생성

위 factorial(3) 예제에서 호출 스택이 어떻게 동작하는지 살펴보면 다음과 같다.

1. factorial(3)을 호출하며 시작한다. 하지만 factorial(3)이 종료되기 전 factorial(2)가 호출되고, 컴퓨터는 factorial(3)이 아직 실행 중임을 알기 위해 이 정보를 호출 스택에 푸시(push)한다.

   현재 호출 스택
   factorial(3)

2. 컴퓨터는 이어서 호출된factorial(2)를 실행한다. 그리고 factorial(2)가 종료되기 전 factorial(1)이 호출되므로, factorial(2)가 아직 실행 중임을 알기 위해 마찬가지로 호출 스택에 푸시(push)한다.

   현재 호출 스택
   factorial(2)
   factorial(3)

3. 컴퓨터는 이어서 호출된 factorial(1)을 실행한다. 1은 기저 조건에 해당하므로 또 다시 함수를 호출하지 않고 1을 리턴하며 끝내며, 호출 스택을 확인해 실행 중이던 함수가 있는지 체크한다. 스택은 LIFO 구조로서 마지막 요소만 접근할 수 있으므로, 가장 최근에 실행됐던 함수 factorial(2)를 팝(pop)한다.

   현재 호출 스택
   factorial(3)

4. 컴퓨터는 꺼낸 factorial(2)의 실행을 완료하고, 다시 호출 스택을 확인해 최근 실행 중이던 함수를 확인하여 facotorial(1)을 팝(pop)한다.

   현재 호출 스택
   ﾠ

5. facotial(3)의 실행을 완료한다. 호출 스택이 비어있으므로 모든 실행이 완료되었고 재귀가 종료된다.

factorial 함수는 재귀 기반의 계산법이다. 이러한 방법을 호출 스택을 통해 값 위로 전달하기(passing a value up through the call stack)라고 부르기도 한다. 즉, 각 재귀 함수는 계산된 값을 부모 함수에 반환하며, 최초로 호출된 함수가 최종 값을 계산하게 된다.

스택 오버플로

스택 오버플로(Stack Overflow)란?
프로그램이 호출 스택에서 이용 가능한 공간 이상을 사용하려고 시도할 때, 또는 지정된 시스템 메모리 사이즈보다 과다한 스택 메모리를 사용할 때 스택 오버플로(overflow)가 발생한다.

들어가기 전에 파트에서 blah() 는 자기 자신을 무한대로 호출한다. 이 때 컴퓨터의 호출 스택은 같은 함수를 반복해서 호출 스택에 푸시하게 되고, 단기 메모리에 더이상 데이터를 저장할 공간이 없을 때까지 호출 스택이 늘어나 결국 스택 오버플로 오류가 발생하게 된다. 이후 강제로 재귀를 중단시켜 "메모리가 다 찼으니 더이상 함수 호출은 거부한다!"고 외친다.

10.5 파일시스템 순회

재귀는 몇 단계나 깊이 들어가야 할지 모르는 상황에서 문제를 여러 단계로 파고 들어가야 할 때 유용하다.

만약 어떤 디렉토리 내에 있는 모든 파일에 대해서 모든 하위 디렉토리명을 출력하는 코드가 있다고 할 때, 자바스크립트로는 다음과 같이 구현할 수 있다. (Node.js 환경에서 동작)

❗️ 이번 예제는 책의 루비 코드를 ChatGPT의 도움을 받아 자바스크립트로 변환한 버전으로, 정상적으로 작동하지 않을 수 있습니다...🥲

const fs = require('fs');
const path = require('path');

function findDirectory(directory) {
    fs.readdir(directory, (err, files) => {
        if (err) {
            console.error(err);
            return;
        }

        files.forEach(filename => {
            const fullPath = path.join(directory, filename);
            fs.stat(fullPath, (err, stats) => {
                if (err) {
                    console.error(err);
                    return;
                }

                if (stats.isDirectory() && filename !== "." && filename !== "...") {
                    console.log(fullPath);
                }
            });
        });
    });
}

이 스크립트는 주어진 디렉토리 내 각 파일을 순회하며 파일이 하위 디렉토리면 하위 디렉토리 명을 출력한다. (단, 현재 디렉토리를 뜻하는 마침표(.)나 이전 디렉토리를 뜻하는 쌍마침표(..)가 아닌 경우에만)

하위의 하위 디렉토리명을 출력할 수 있도록 코드를 업데이트 하면 아래와 같다.

const fs = require('fs');
const path = require('path');

function findDirectories(directory) {
    fs.readdir(directory, (err, files) => {
        if (err) {
            console.error(err);
            return;
        }

        files.forEach(filename => {
            const fullPath = path.join(directory, filename);
            fs.stat(fullPath, (err, stats) => {
                if (err) {
                    console.error(err);
                    return;
                }

                if (stats.isDirectory() && filename !== "." && filename !== "..") {
                    console.log(fullPath);

                    fs.readdir(fullPath, (err, innerFiles) => {
                        if (err) {
                            console.error(err);
                            return;
                        }

                        innerFiles.forEach(innerFilename => {
                            const innerFullPath = path.join(fullPath, innerFilename);
                            fs.stat(innerFullPath, (err, innerStats) => {
                                if (err) {
                                    console.error(err);
                                    return;
                                }

                                if (innerStats.isDirectory() && innerFilename !== "." && innerFilename !== "..") {
                                    console.log(innerFullPath);
                                }
                            });
                        });
                    });
                }
            });
        });
    });
}

위 코드는 디렉토리의 하위 디렉토리에 대해 동일한 루프를 수행하여 하위 디렉토리명을 출력한다.

😧 만약 3단계, 4단계 아래에 있는 하위 디렉토리에 접근하고 싶다면?

해당하는 단계까지 접근할 수 있는 중첩 루프를 사용해야 한다.

🤯 하위 디렉토리가 더이상 없을 때까지 찾고싶다면?

하위가 몇 단계 존재하는지 알 수 없으므로 중첩 루프로 실행할 수 없다.

바로 이 때 재귀를 유용하게 사용할 수 있다.
재귀를 사용하여 원하는 만큼 하위 디렉토리로 내려가는 코드를 작성할 수 있고 매우 간단하게 구현 가능하다.

const fs = require('fs');
const path = require('path');

function findDirectories(directory) {
    fs.readdir(directory, (err, files) => {
        if (err) {
            console.error(err);
            return;
        }

        files.forEach(filename => {
            const fullPath = path.join(directory, filename);
            fs.stat(fullPath, (err, stats) => {
                if (err) {
                    console.error(err);
                    return;
                }

                if (stats.isDirectory() && filename !== "." && filename !== "..") {
                    console.log(fullPath);
                    findDirectories(fullPath); // 재귀!
                }
            });
        });
    });
}

(위 알고리즘은 추후 깊이 우선 탐색(DFS)에서 다시 한 번 다룰 수 있다.)

실습

1. 다음 함수는 low부터 high까지의 수를 하나 걸러 하나씩 출력한다. 이 함수의 기저 조건은?

function printEveryOther(low, high) {
	if (low > higth) return;
  	
  	console.log(low);
  	printEveryOther(low + 2, high);
}

정답 : if (low > higth)
low가 high보다 클 때 재귀를 멈추기 때문에 이 부분이 기저 조건

2. 다음 함수로 factorial(10)을 실행하면 나오는 값은?

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

정답 : 무한 호출
10에서 2씩 감소하면 절대 1이 될 수 없으므로 number === 1이 되는 순간이 오지 않음

3. 다음 함수는 low부터 high까지 모든 수의 합을 반환한다. 그러나 기저 조건이 빠져있어 무한대로 실행된다. 올바른 기저 조건을 넣어 코드를 수정하자.

function sum(low, high) {
	return high + sum(low, high - 1);
}

정답 :

function sum(low, high) {
	if (low === high) return low;
  	return high + sum(low, high - 1);
}

4. 다음 배열은 숫자와 배열을 포함하며, 이 때 배열은 다시 숫자와 배열을 포함할 수 있따. 배열 내 모든 숫자만 출력하는 재귀 함수를 작성하라.

const array = [
	1,
  	2, 
  	3, 
  	[4, 5, 6],
  	7,
  	[8, [9, 10, 11, [12, 13, 14]]],
    [15, 16, 17, 18, 19, [20, 21, 22, [23, 24, 25, [26, 27, 29]], 30, 31], 32],
    33
];

정답 :

function printOnlyNumber(array) {
	for (const value of array) {
    	if (typeof value === "number") {
        	console.log(value);
        } else printOnlyNumber(value);
    }
}

요약

• 재귀란 재귀는 자신을 정의할 때 자기 자신을 재참조하는 방법으로 프로그래밍에서는 재귀호출(Recursive Call) 형태로 많이 사용된다.
• 루프를 사용할 수 있는 경우라면 대부분 재귀도 사용할 수 있으며, 무조건 써야한다는 건 아니다.
• 모든 재귀 함수에서는 함수가 무한대로 호출되지 않도록 제어하는 기저 조건이 최소 1개 존재해야 한다.
• 기저 조건이 없어 무한대로 호출되는 재귀 함수는 메모리 초과로 인해 스택 오버플로 오류가 발생한다.
• 컴퓨터는 재귀를 실행하기 위해 호출 스택에 실행 함수를 저장하여 기억한다.