[TIL] 재귀 함수

Jeris·2023년 4월 13일

JavaScript algorithm

코드잇 부트캠프 0기

목록 보기

29/107

Topic

Recursive function
Iteration

What I Learned

1. 재귀 함수

재귀 함수(Recursive Function)란?

자기 자신을 호출하는 함수

재귀 활용 예시

재귀적 문제 풀이: 부분 문제(Subprorblem)의 답을 이용해서 기존 문제를 푸는 것
- 부분 문제(Subproblem): 같은 형태의 더 작은 문제
- factorial
  - (base case) n=0인 경우: n! = 1
  - (recursive case) n>0인 경우: n! = (n-1)! * n
```
// recursive function
function factorial(n) {
  if (n === 0) {
    return 1;
  }
  return factorial(n - 1) * n
}
```
  - Worst-case time complexity: O(n)
  - Best-case time complexity: O(n)
  - Average time complexity: O(n)
  - Worst-case space complexity: O(n)
  - Best-case space complexity: O(n)
  - Average space complexity: O(n)
```
// iteration
function factorial(n) {
  let result = 1;
  for (let i = 1; i < n + 1; i += 1) {
    result *= i;
  }
  return result;
}
```
  - Worst-case time complexity: O(n)
  - Best-case time complexity: O(n)
  - Average time complexity: O(n)
  - Worst-case space complexity: O(1)
  - Best-case space complexity: O(1)
  - Average space complexity: O(1)

재귀 함수 vs. 반복문

반복문으로 풀 수 있는 문제는 재귀 함수로 풀 수 있다.
재귀 함수로 풀 수 있는 문제는 반복문으로 풀 수 있다.
재귀 함수 호출이 너무 많으면 콜 스택(Call Stack)이 계속해서 쌓이면서 StackOverflowError가 발생한다.
- 콜 스택(Call Stack): 프로그램이 현재 실행중인 서브루틴에 대한 정보를 저장하는 스택 데이터 구조
- 파이썬은 콜 스택을 1,000개까지만 허용한다.
콜 스택 문제가 일어나지 않을 때, 반복문보다 재귀 함수로 쓰면 코드가 깔끔해지는 문제에는 재귀 함수를 쓰는 것이 좋다.

2. 재귀 함수 연습

피보나치 수열

function fib(n) {
  // base case
  if (n < 3) {
    return 1;
  }

  // recursive case
  return fib(n - 1) + fib(n - 2);
}

// test code
for (let i = 0; i < 11; i += 1) {
  console.log(fib(i));
}

Worst-case time complexity: O(2^n)
Best-case time complexity: O(2^n)
Average time complexity: O(2^n)
Worst-case space complexity: O(n)
Best-case space complexity: O(n)
Average space complexity: O(n)

function fib(n) {
  // base case
  let current = 1;
  let previous = 1;

  // recursive case
  for (let i = 1; i < n; i += 1) {
    temp = previous;
    previous = current;
    current = current + temp;
  }

  return current;
}

// test code
for (let i = 0; i < 11; i += 1) {
  console.log(fib(i));
}

Worst-case time complexity: O(n)
Best-case time complexity: O(n)
Average time complexity: O(n)
Worst-case space complexity: O(1)
Best-case space complexity: O(1)
Average space complexity: O(1)

리스트 뒤집기

function flip(some_list) {
  // base case
  if (some_list.length <= 1) {
  return some_list;
  }

  // recursive case
  return some_list.slice(-1).concat(flip(some_list.slice(0, -1)));
}

# test code
console.log(flip([1,2,3,4,5]))

Worst-case time complexity: O(n^2)
Best-case time complexity: O(1)
Average time complexity: O(n^2)
Worst-case space complexity: O(n^2)
Best-case space complexity: O(n)
Average space complexity: O(n^2)

하노이의 탑

하노이의 탑(Tower of Hanoi) 참조

function move_disk(disk_num, start_peg, end_peg) {
  console.log(`${disk_num}번 원판을 ${start_peg}번 기둥에서 ${end_peg}번 기둥으로 이동`);
}

function hanoi(num_disks, start_peg, end_peg) {
  // base case
  if (num_disks === 1) {
    move_disk(1, start_peg, end_peg);
  }

  // recursive case
  else {
    hanoi(num_disks - 1, start_peg, 6 - start_peg - end_peg);
    move_disk(num_disks, start_peg, end_peg);
    hanoi(num_disks - 1, 6 - start_peg - end_peg, end_peg);
  }
}

// test code
hanoi(3, 1, 3);

Worst-case time complexity: O(2^n)
Best-case time complexity: O(2^n)
Average time complexity: O(2^n)
Worst-case space complexity: O(n)
Best-case space complexity: O(n)
Average space complexity: O(n)

Feedback

하노이의 탑같은 문제는 생각하는 과정이 재밌다.
일반적인 알고리즘 이론이나 방법, 복잡도 등은 다루지 않고 재귀 함수를 활용하는 법만 짧게 다뤘다.
코드잇 알고리즘 콘텐츠를 전부 수강한 뒤, 'Cracking the Coding Interview' 책과 Leetcode 사이트로 알고리즘을 계속 공부할 예정이다.
다음으로 '좋은 알고리즘이란?' 코드잇 콘텐츠를 수강할 예정이다.
리스트 뒤집기, 하노이의 탑 복잡도를 더 줄여보자.