CS) 재귀를 사용한 재귀적 반복

김명성·2023년 6월 14일

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

재귀를 올바르게 사용하면 까다로운 문제 유형을 놀랍도록 간단하게 풀 수 있다.

때로는 마법처럼 보일 정도다!

function blah() {
  blah()
}

위 함수는 blah()가 자신을 무한으로 호출하게 된다.

재귀는 함수가 자기 자신을 호출할 때를 뜻하는 용어다.

이 예제와 같은 무한 재귀는 전혀 쓸모가 없지만, 올바르게만 활용하면 재귀는 강력한 도구가 될 수 있다.

루프 대신 재귀

당신은 지금 NASA에서 일하고 있고 우주선 발사에 쓰일 카운트다운 함수를 프로그래밍해야 한다.

작성할 함수는 10과 같은 숫자를 받아 10부터 0까지 숫자를 표시해야 한다.

잠시 쉬면서 이 함수를 원하는 언어로 구현해 보자.

아마 십중팔구 간단한 루프로 작성했을 것이다.

구현에는 문제가 없지만 루프 자체가 필요하지 않았을 수도 있다.

루프 대신에 재귀를 사용해보자

다음은 재귀로 카운트다운 함수를 구현한 첫 번째 시도다.

function countdown(number) {
  console.log(number)
  if(number >=0) {
    countdown(number -1)
  }
}

재귀를 계속 살펴보기전에 어떤 방식으로 재귀를 이용해 목적을 달성하는지 짚고 넘어가자.

루프 구조체 없이 단순히 countdown 함수 호출만으로 10부터 카운트다운해서 각 숫자를 콘솔에 출력하고 있다.
루프를 사용할 수 있는 경우라면 거의 대부분 재귀도 쓸 수 있다.

물론 재귀를 쓸 수 있다는 이유만으로 무조건 재귀를 써야 한다는 것은 아니다.

재귀는 명쾌한 코드를 작성해 줄 수 있는 하나의 도구다.

앞선 예제의 경우 재귀적인 방법이 루프보다 더 훌륭하거나 효율적이지는 않다.

재귀의 기저 조건

재귀에 쓰이는 용어로 함수가 반복되지 않게 막는 조건을 기저 조건이라 부른다.
예제의 countdown()함수는 0이 기저 조건이다.
모든 재귀 함수에는 무한대로 호출되지 않게 하는 기저 조건이 적어도 하나는 존재해야 한다.

재귀 코드 읽기

factorial을 계산하는 예제를 살펴보자.

factorial은 예제로 가장 잘 설명된다.

3의 factorial은 3 * 2 * 1 = 6 이다.
5의 factorial은 5 * 4 * 3 * 2 * 1 이다.

코드로 작성해보자

function factorial(num) {
  if(num === 1) return 1;
  return num * factorial(num -1);
}
factorial(5);

재귀를 읽는 연습을 해보자.

기저 조건을 찾는다.
기저 조건에서 함수가 어떻게 동작하는지 살핀다.
"끝에서 두 번째" 조건을 찾는다. 곧 보이겠지만 이는 기저 조건 바로 전 조건이다.
"끝에서 두 번째" 조건에서 함수가 어떻게 동작하는지 살핀다.
방금 분석한 조건의 바로 전 조건을 찾아가며 위 절차를 반복하고 그때마다 함수가 어떻게 동작하는지 살핀다.

기저 조건은 num === 1이다.
기저조건일 때 함수는 factorial(1)을 호출하면 메서드는 1을 반환한다.
factorial(1) return 1
끝에서 두 번째 조건은 num = 2이다.
num이 2라면 기저조건에 해당하지 않으므로 2 * factorial(1) = 2를 반환한다.
factorial(2) return 2
factorial(1) return 1
끝에서 세 번째 조건은 num === 3이다.
num이 3이라면 3 * factorial(2) = 6을 반환한다.
factorial(3) return 6
factorial(2) return 2
factorial(1) return 1
끝에서 네 번째 조건은 num ===4이다.
num이 4라면 4 * factorial(3) = 24를 반환한다.
factorial(4) return 12
factorial(3) return 6
factorial(2) return 2
factorial(1) return 1
num이 5라면 5 * factorial(4) = 120을 반환한다.
factorial(5) return 120
factorial(4) return 24
factorial(3) return 6
factorial(2) return 2
factorial(1) return 1

5의 factorial은 5 * 4 * 3 * 2 * 1 = 120이다.

어떻게 이런 결과가 나오는걸까? 컴퓨터의 관점으로 과정을 살펴보자

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

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

인간은 앞서 본 방법으로 재귀를 추론할 수 있지만 컴퓨터는 함수 내에서 다시 그 함수를 호출하는 복잡한 작업을 수행해야 한다.

컴퓨터가 재귀 함수를 실행하는 절차를 나눠서 살펴보자

가령 factorial(3)을 호출한다고 하자.
3은 기저조건이 아니므로 컴퓨터는 다음 코드 줄로 가서 함수 factorial(2)를 실행한다.

return number * factorial(number - 1)

이때 주목해야 할 점은 컴퓨터가 factorial(2)를 실행을 시작할 때 아직 factorial(3)의 실행은 끝나지 않았다는 점이다.

그래서 재귀가 까다로운 것이다. 컴퓨터가 factorial(3)의 코드의 함수 몸체를 닫는 괄호에 도달할 때까지 factorial(3)은 끝나지 않는다.

결국 컴퓨터는 아직 factorial(3)을 다 실행하지 않았는데 factorial(2)를 시작하는 것이다.

게다가 factorial(2)가 factorial(1)을 실행시키니 factorial(2) 또한 끝이 나지 않았다.

결국 factorial(1)은 factorial(2)와 factorial(3) 두 함수의 호출을 실행하는 중 실행되는 것이다.

컴퓨터는 이러한 정보를 어떻게 전부 기록할 수 있을까?

factorial(1)이 끝나면 다시 돌아가 factorial(2)를 마저 실행해야 한다는 사실을 기억해야 하고, factorial(2)가 끝난 뒤 factorial(3)까지 완료해야 한다는 사실도 기억해야 한다.

Call Stack ( 호출 스택 )

다행히도 바로 앞에서 스택을 배웠다.
컴퓨터는 스택을 사용해 어떤 함수를 호출 중인지 기록한다.
이 스택을 목적에 딱 맞게 호출 스택이라 부른다.

처음부터 정리해보자
factorial(3)을 호출한다.
컴퓨터가 아직 factorial(3)을 실행중인지 알려면 이 정보를 호출 스택에 푸시해야 한다.

Call Stack
`factorial(3)`

이어서 컴퓨터는 faactorial(2)를 실행한다. 이제 factorial(2)는 연이어 factorial(1)을 호출한다.
하지만 factorial(1)을 실행하기 전에 컴퓨터는 아직 factorial(2)를 실행중임을 기억해야 하므로 호출 스택에 푸시한다.

Call Stack
`factorial(2)`
`factorial(3)`

이어서 컴퓨터는 factorial(1)을 실행한다.
1이 기저조건이므로 factorial(1)은 factorial 메서드를 더이상 호출하지 않고 값을 반환하며 끝낸다.

컴퓨터는 factorial(1)을 끝낸 후 호출 스택을 확인해 실행 중이던 함수가 있는지 본다.
호출 스택에 데이터가 있으면 컴퓨터에 아직 할 일이 남아있다는 뜻이며 실행 중인 다른 함수를 마무리해야 한다는 뜻이다.

스택은 LIFO의 구조이므로 호출 스택의 가장 마지막에 호출했던 함수를 가장 먼저 완료해야 한다.

컴퓨터가 다음으로 할 일은 호출 스택 가장 위 원소factorial(2)를 factorial(1)의 반환 값을 토대로 완료한다. num * factorial(1)
factorial(1)의 반환값은 1 이므로 2 * 1 = 2가 된다.

Call Stack
~~`factorial(2)`~~
`factorial(3)`

호출 스택에는 factorial(3)만 남아있다.
factorial(2)의 반환 값을 토대로 완료한다. num * factorial(2)
factorial(2)의 반환 값은 2이므로 3 * 2 = 6이 된다.

Call Stack
~~`factorial(3)`~~

이렇게 재귀에 기반한 계산은 호출 스택의 가장 마지막에 입력된 함수의 결과가 그 다음 콜 스택의 Top에 위치한 함수의 값으로서 전달됨으로 인해 이뤄진다.

이러한 방법을 호출 스택을 통해 값 위로 전달하기라고 부르기도 한다.
즉 각 재귀 함수는 계산된 값을 부모 함수에 반환한다.

주의점 : Stack Overflow

제일 상단에 예시를 들었던 blur() 함수는 자기 자신을 무한정 호출했다.
무한 재귀에서는 같은 함수를 호출 스택에 계속 푸시하며 단기 메모리에 더 이상 데이터를 저장할 공간이 없을 때까지 증가한다.
결국 Stack Overflow에러가 발생한다.
컴퓨터는 재귀를 강제로 중단하고 오류를 throw한다.

연습문제. 파일시스템 순회

재귀가 어떻게 동작하는지 이해했으니 재귀 없이는 풀기 어려웠을 문제를 해결할 수 있다.

재귀와 자연스럽게 들어맞는 한 가지 문제 유형은 깊이를 알 수 없는 단계에서 문제를 여러 단계로 파고 들어야 할 때이다.

파일시스템을 순회하는 예제로 살펴보자.
어떤 디렉터리 내에 있는 모든 파일에 대해 모든 하위 디렉터리 명을 출력하는 등의 작업을 하는 스크립트가 있다고 하자.

단 하나의 디렉터리 내에 있는 파일이 아닌 더 이상 하위파일이 없을 때까지 수행되길 원한다.

var fs = require('fs');

function searchAllDirectory(dir) {

    var files = fs.readdirSync(dir);
    var result = [];
    files.forEach((file) =>{
        let filePath = dir + '/' + file;
        let stat = fs.statSync(filePath);
		stat.isDirectory());
        ? result = [...result,...searchAllDirectory(filePath)];
        : result.push(filePath);
        }
    })
    return result;
}
searchAllDirectory('.')

파일시스템 순회 재귀 함수의 작동 단계

readdirSync 메서드는 디렉터리의 내용을 조회한다. 즉 현재 디렉터리를 기준으로 디렉터리에 포함된 것들을 읽어들인다.
읽어들인 파일들을 순회하여 filePath를 입력해준다.
최초의 filePath는 ./ + 파일의 이름일 것이다.
filePath를 statSync 메서드를 통해 주어진 파일 경로./foo에 대한 정보를 동기식으로 반환한다. 반환된 객체를 stat이라 부르며 stat 객체에는 파일에 대한 여러 필드와 메서드가 존재한다.
stat 객체의 isDirectory()메서드를 사용하여 현재 읽고 있는 stat이 파일인지 / 디렉터리인지 확인한다.
디렉터리라면 result 배열에 담아주면서 다시 searchAllDirectory 함수를 실행한다. 예시로 filePath가 ./foo인 디렉터리가 존재한다고 가정하겠다.
아직 searchAllDirectory('.') 아직 종료되지 않은 상태이다.
2번째 searchAllDirectory 함수로 진입한다 dir = ./foo이다.
./foo 디렉터리에 포함된 파일, 폴더를 읽는다.
./foo 디렉터리에는 bar.js, zar.js 파일이 존재한다.
foo 디렉터리를 순회하며 filePath를 생성한다.
./foo + / + bar.js = ./foo/bar.js
stat 객체로 변환한다.
bar.js는 디렉터리가 아닌 파일이므로 result 배열에 푸쉬된다.
./foo + / + zar.js = ./foo/zar.js
stat 객체로 변환한다.
zar.js는 디렉터리가 아닌 파일이므로 result 배열에 푸쉬된다.
더이상 디렉터리가 없어 재귀를 실행할 수 없는 기저조건이 달성되었다.
2번째 searchAllDirectory 함수를 종료한다.
파일이 A-Z 오름차순으로 정렬되어있다면 foo 디렉터리의 다음의 정렬 순서부터 첫번째 searchAllDirectory 함수가 실행된다.
더 이상 디렉터리가 없다면 첫번째 searchAllDirectory 함수의 기저조건이 달성되었으므로 함수는 종료된다.