자료구조 알고리즘 2주차 - 메옹님의 블로그 - 인프런

재귀 (Recursion)

재귀 구현

함수가 자기 자신을 호출하는 방식
기본적으로 종료 조건(Base case) 과 반복 호출(Recursive case) 로 구성됨

const myFunc = (number) => {
  if (number > 10) return;
  console.log(number);
  myFunc(number + 1);
};

myFunc(1);

종료가 없는데 자동으로 실행이 종료된 이유?

종료 조건이 없거나 충족되지 않으면 무한 반복
콜스택(Call Stack)이 계속 쌓여서 메모리 한계를 넘으면 스택 오버플로우(Stack Overflow) 발생 후 프로그램 강제 종료됨

콜스택의 개념

함수 호출 정보를 저장하는 메모리 구조 (LIFO)
재귀 호출이 일어날 때마다 스택에 함수 상태(매개변수, 지역변수 등) 가 쌓임
호출이 끝나면 스택에서 빠져나가며 이전 상태로 돌아감

재귀를 사용하는 이유

문제를 더 작은 하위 문제로 나눠서 풀기 좋을 때 유리
예시 : 팩토리얼, 피보나치 수열, 트리 탐색, 하노이탑 등
반복문보다 코드가 간결하고 직관적일 수 있음

재귀적으로 생각하기

재귀의 여러 가지 패턴 분석하기

단순 반복 구현
- 반복문(for/while)으로 충분한데 재귀를 쓰면 비효율적 (콜스택 부담)
하위 문제 결과를 기반으로 현재 문제 계산
- 예시: 팩토리얼(n!) = n * (n-1)!
- 하향식(Top-down): 큰 문제에서 시작 → 하위 문제를 해결하며 내려감
- 상향식(Bottom-up): 작은 문제부터 차례로 풀어서 큰 문제를 해결 (재귀보다는 반복문과 DP에 주로 사용)

어떤 종류의 재귀 함수인지 구분하기

단순 재귀: 하위 문제를 그대로 호출 (ex. 팩토리얼)

const power = (x, n) => {
  if (n === 0) return 1;

  return power(x, n - 1) * x;
};

console.log(power(2, 5));

const strLength = (arr) => {
  if (arr[0] === undefined) return 0;
  return strLength(arr.slice(0, -1)) + 1;
};

let str = "abcde";
let len = strLength(str);
console.log(len);

const factorial = (num) => {
  if (num === 1 || num === 0) return 1;
  return num * factorial(num - 1);
};

console.log(factorial(5));

다중 재귀: 여러 번 호출하는 경우 (ex. 피보나치)
트리 재귀: 트리 구조 탐색 (ex. DFS)
꼬리 재귀: 마지막에 자기 자신 호출 → 반복문으로 최적화 가능

재귀의 위력을 느낄 수 있는 문제

하노이탑
트리 탐색 (DFS)
백트래킹 (경로 탐색, 조합, 순열 문제)

재귀를 쉽게 사용할 수 있는 방법

종료 조건을 명확히 설계
스택 오버플로우 방지 위해 입력값 제한 또는 반복문 전환 고려
메모이제이션(Memoization) 으로 중복 계산 제거

하노이탑

가장 대표적인 재귀 문제
원판을 한 개씩 이동시키는 재귀적 패턴
이동 순서가 명확하고, 규칙에 따라 분할 정복 가능
최소 이동 횟수: 2ⁿ - 1

// 원반의 갯수, 시작 기둥(from), 이동할 기둥(to), 임시로 사용할 수 있는 기동(temp)
const hanoi = (count, from, to, temp) => {
  if (count === 0) return;
  hanoi(count - 1, from, temp, to);
  console.log(`원반 ${count}를 ${from}에서 ${to}로 이동`);
  hanoi(count - 1, temp, to, from);
};

hanoi(3, "A", "C", "B");

버블 정렬 (Bubble Sort)

핵심 개념

인접한 두 값을 비교하고 교환하며 정렬
매번 가장 큰 값을 뒤로 밀어내는 방식 → 버블처럼 부상하는 느낌

for문 두 개가 중첩됨

외부 루프: 전체 패스 반복 (n-1회)
내부 루프: 인접 요소 비교 및 교환 (n-i-1회)

시간 복잡도

O(n²)
등차수열의 합: (n-1) + (n-2) + … + 1 = n(n-1)/2
데이터가 많아지면 급격히 느려짐

const bubbleSort = (arr) => {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
};

선택 정렬 (Selection Sort)

핵심 개념

최솟값을 찾아서 맨 앞과 교환하는 방식
한 번 선택한 요소는 다시 고려하지 않음 → 안정성은 없음

성능

for문 두 개가 중첩
- 외부 루프: 정렬 범위 축소
- 내부 루프: 최솟값 탐색

시간 복잡도 O(n²) → 버블 정렬과 비슷한 비효율성

const selectronSort = (arr)=>{
    for(let i = 0 ; i < arr.length - 1 ; i++){
        let minValueIndex = i;

        for(let j = i + 1 ; j < arr.length; j++){
            minValueIndex = j;
        }

        let temp = arr[i];
        arr[i] = arr[minValueIndex];
        arr[minValueIndex] = temp;
    }
}

회고..

배운 내용 & 내 생각

재귀
재귀는 단순히 "함수가 자기 자신을 호출하는 것"이라고만 알고 있었는데,
이번에 콜스택과 메모리 구조를 이해하고 나니까 재귀 호출이 어떻게 돌아가는지 시각화가 됐다.
특히 종료 조건(Base case)이 왜 중요한지 체감했다.
종료 조건을 제대로 못 걸면 콜스택이 무한히 쌓이다가 스택 오버플로우가 발생한다는 걸 코드로 실험해보며 확인했다.

팩토리얼이나 피보나치 같이 작은 문제로 쪼개서 풀어가는 방식은 하향식(Top-down),
반복문이나 동적 계획법으로 밑에서부터 쌓아가는 건 상향식(Bottom-up)이라는 개념이 머릿속에 좀 더 명확해졌다.

정렬 알고리즘
버블 정렬과 선택 정렬은 사실 비슷한 느낌인데, 다시 보면 비효율적인 방식이라는 걸 알게 됐다.
특히 시간 복잡도 O(n²)를 등차수열의 합으로 직접 계산해보니 훨씬 더 와닿았다.
그럼에도 불구하고 이런 정렬부터 배우는 이유는, 기초적인 반복과 비교 구조를 이해하기 위해서라는 생각이 들었다.

어려웠던 점과 해결 방법
재귀에서 하향식과 상향식 사고가 헷갈렸는데,
직접 코드를 그려보고 함수 호출 순서와 콜스택 흐름을 손으로 써보니까 감이 잡혔다.
또, 하노이탑 문제를 풀면서 "문제를 나누고, 나눈 문제를 어떻게 다시 합칠지"를 생각하는 패턴이 중요한 걸 느꼈다.

적용과 앞으로의 계획
재귀적인 사고를 백트래킹 문제에 적용해보고 싶다.
예를 들어 DFS 기반 조합, 순열, 경로 탐색 문제를 풀어보면서 패턴을 익힐 예정이다.
정렬 알고리즘은 이제 퀵 정렬, 병합 정렬 같은 효율적인 방식으로 넘어가야겠다.

또한, 재귀는 단순한 반복의 다른 표현이 아니라, 문제를 쪼개서 푸는 사고법이다.
이걸 익히면 알고리즘 문제에서 트리 구조나 백트래킹을 자연스럽게 생각할 수 있다.