[인프런 워밍업 클럽 3기 - CS] - 2주차 미션 (자료구조와 알고리즘)

재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?

재귀함수는 함수 내부에서 자기 자신을 다시 호출하여 작업을 수행하는 함수를 의미한다. 즉, 자기 자신을 무한대로 호출하여 작업하기 때문에 함수 종료 조건인 기저조건을 설정하지 않는다면, 해당 함수가 실행됨에 따라 무한대로 콜스택에 메모리가 얹히게 되고 스택 오버플로우가 발생하여 프로그램이 강제 종료된다.

// 기저 조건 없는 경우
function factorial(n){
    return n * factorial(n - 1)
}

// RangeError : Maxmum call stack size exceeded

// 기저 조건 설정
function factorial(n) {
  if (n == 0) return 1;
  return n * factorial(n - 1);
}

0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.

하위조건 : n - 1이 홀수인지 확인하고 홀수일 경우 n을 더하고 짝수일 경우 0을 더함

기저조건: n이 0 이하일 경우 0을 반환하고 함수 종료

function sumOdd(n){
  // 재귀 로직
  if (n <= 0) return 0;
  let oddNum = n % 2 === 0 ? 0 : n;

  return oddNum + sumOdd(n - 1);
}

console.log(sumOdd(10)) // 25

다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요.

const fs = require('fs'); // 파일을 이용하는 모듈
const path = require('path'); // 폴더와 파일의 경로를 지정해주는 모듈

function traverseDirectoryRecursive(directory) {
  const files = fs.readdirSync(directory);        // 1. 인자로 받은 폴더 내부 파일들 추출

  for (const file of files) {
    const filePath = path.join(directory, file);  // 2. 파일 경로 합치기
    const fileStatus = fs.statSync(filePath);     // 2. 파일 정보 얻기

    if (fileStatus.isDirectory()) {               // 3-1. 폴더일 경우 재귀
      console.log('디렉토리:', filePath);
      traverseDirectoryRecursive(filePath);       
    } else {                                      // 3-2. 파일일 경우 출력
      console.log('파일:', filePath);
    }
  }
}

traverseDirectoryRecursive('.'); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력

하위 조건:

인자로 받은 Directory의 파일과 폴더를 읽어온다
파일 경로를 합치고 파일 정보를 얻어온다
폴더일 경우, 재귀함수를 통해 내부 폴더의 파일과 폴더를 읽는다
파일일 경우, 파일을 출력한다.

기저조건:

현재 폴더 내부 모든 파일 수만큼 반복

📔 회고
알고리즘 문제가 아닌 실전에서 사용할 수 있는 재귀 함수로 응용을 해보니 생각보다 하위조건을 파악하고 기저조건을 설정하는 것이 쉽지 않다는 것을 깨달았다. 처음에는 계속해서 코드를 읽어보면서 익숙하지 않은 fs모듈에 대해서 먼저 파악해보고, 제공되는 메서드들을 익혀보았다. 그렇게 코드의 흐름을 익혀가면서 반복되는 부분을 구분하였고, 재귀적으로 해결할 수 있는 부분은 while 문이라는 것을 파악했다.

기존에 스택을 통해서 파일들을 가져오고 데이터를 쌓아오면서 while 문을 통해 스택에 있는 데이터를 다시 출력하는 코드였다는 것을 파악하였고, 이를 재귀적으로 변경하기 위해서는 스택 자료구조를 사용하지 않고 하나의 함수에 하나의 폴더를 읽어오고 재귀적으로 함수를 다시 호출하면서 폴더 내부의 파일을 찾아가는 형식으로 수정할 수 있다는 것을 파악했다. 그렇게 하위조건을 설정하였고 기저조건을 만들어서 성공적으로 재귀함수로 코드를 수정할 수 있었다.

이렇게 알고리즘을 응용하여 실전에서 사용할 수 있다는 것을 크게 깨달았고, 앞으로 알고리즘을 배울 때도 실전에서도 사용될 수 있는 다양한 사례를 함께 찾아보면서 공부하면 더 알고리즘 개념을 탄탄히 가져갈 수 있을 것 같다.

[인프런 워밍업 클럽 3기 - CS] - 2주차 미션 (자료구조와 알고리즘)

📔 회고