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)
하노이의 탑
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 사이트로 알고리즘을 계속 공부할 예정이다.
- 다음으로 '좋은 알고리즘이란?' 코드잇 콘텐츠를 수강할 예정이다.
- 리스트 뒤집기, 하노이의 탑 복잡도를 더 줄여보자.
Reference
job's done