[워밍업 클럽 3기 CS 전공지식] 2주차 자료구조와 알고리즘 미션

2025-03-15T09:28:33.750Z

wonderson

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

재귀 함수가 계속 자신을 호출하면서 콜스택에 쌓이게 됩니다.
콜스택에 메모리 공간이 가득차서 원하는 결과를 얻지 못하고 자동으로 종료됩니다.

0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.
1. 코드 작성 전 생각해보기
  1. num 이 홀수인지 짝수인지 구하기
    1. 홀수면 그대로 사용하고 짝수면 num-1 을 하기
  2. 더해서 결과를 보여줘야 하니 반환되는 값이 필요합니다. (반환 타입 int)
  3. 이미 해결을 한 상황을 예상해보기 (하위 문제)
    1. num + sumOdd(num-2)
    2. 홀수에서 -2 하면 홀수입니다.
  4. 기저 조건(탈출 조건)
    1. 1까지 도달했을 때 더이상 -2로 홀수를 찾아올 수 없으므로 값 그대로 1을 반환합니다.

public static int sumOdd(int num) {
    // 기저 조건 (탈출 조건)
    if (num == 1) return 1;
    // 처음 들어온 num 이 짝수인 경우 -1로 홀수 만들어주기
    if (num%2==0) num = num - 1;
    return num + sumOdd(num - 2);
}

public static void main(String[] args) {
    System.out.println(sumOdd(10)); // 25
}

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

변경 전

[깃허브 코드 - Java로 작성]

import java.io.File;
import java.util.Stack;

public class FileSearch {
    public static void traverseDirectory(String dir) {
        File startDir = new File(dir);

        Stack<File> stack = new Stack(); // 순회해야 할 디렉토리를 저장할 스택
        File[] startFiles = startDir.listFiles(); // 인자로 주어진 경로의 디렉토리에 있는 파일 or 디렉토리들
        for (int i = 0; i < startFiles.length; i++) {
            stack.push(new File(String.valueOf(startFiles[i])));
        }

        while (!stack.isEmpty()) { // 스택이 빌 때까지 반복
            File currentDir = stack.pop();// 현재 디렉토리
            File[] files = currentDir.listFiles();// 인자로 주어진 경로의 디렉토리에 잇는 파일 or 디렉토리들

            if (files == null) continue;
            
            for (File file : files) { // 현재 디렉토리의 모든 파일 or 디렉토리 순회
                File filePath = new File(currentDir, file.getName()); // directory 와 file 을 하나의 경로로 합쳐줌 및 파일 정보 얻기
//                File fileStatus = new File(String.valueOf(filePath)); // 파일 정보 얻기, 윗 줄과 결과가 같아서 주석

                if (filePath.isDirectory()) { // 해당 파일이 디렉토리라면
                    System.out.println("디렉토리:" + filePath);
                    stack.push(filePath);
                } else { // 해당 파일이 파일이라면
                    System.out.println("파일:" + filePath);
                }
            }
        }
    }

    public static void main(String[] args) {
        traverseDirectory("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력
    }
}

변경 후

코드 작성 전 생각해보기
- 유효성 검사
  - traverseDirectory() 에 매개변수 dir
    - 문자열로 받아와서 값이 null 이거나 빈문자열인지 확인
    - 파일로 만든 후에 '
      디렉토리가 있는지 파일이 있는지' 확인
- traverseDirectory() 안에서 출력하므로 반환없이 void로 설정
- 이미 해결을 한 상황을 예상해보기 (하위 문제)
  - dir 에서 파일, 디렉토리 리스트를 가져오기
  - for문을 반복하면서
    - if 디렉토리면 경로 출력 및 traverseDirectory() 호출
    - else 파일이면 경로 출력
- 기저 조건(탈출 조건)
  - files로 디렉토리에 있는 파일 및 디렉토리를 for문으로 모두 순회하면 자연스럽게 함수를 종료합니다.

[깃허브 코드 - Java로 작성]

import java.io.File;

public class FileSearchRecursion {
    public static void traverseDirectory(String dir) {
        if (dir == null || dir.isEmpty()) return;

        File startDir = new File(dir);

        if (!startDir.exists()) {
            System.out.println(dir + " 디렉토리 또는 파일은 존재하지 않습니다.");
            return;
        }

        File[] files = startDir.listFiles();

        if (files == null) return;

        for (File file : files) {
            File filePath = new File(String.valueOf(file));

            if (filePath.isDirectory()) {
                System.out.println("디렉토리:" + filePath);
                traverseDirectory(filePath.getAbsolutePath()); // 재귀함수 호출
            } else {
                System.out.println("파일:" + filePath);
            }
        }
    }

    public static void main(String[] args) {
        traverseDirectory(".");
    }
}

※ 출처

[인프런 / 그림으로 쉽게 배우는 자료구조와 알고리즘 (감자) / 섹션 3 (유닛 1~5)]

답변 0