스택 자료구조
- 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다.
- 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다.
큐 자료구조
- 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조이다.
- 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화할 수 있다.
재귀 함수
- 재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다.
- 단순한 형태의 재귀 함수 예제
- '재귀 함수를 호출합니다.'라는 문자열을 무한히 출력한다.
- 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력된다.
function recursiveFunction() {
console.log("재귀 함수를 호출합니다.");
recursiveFunction();
}
재귀 함수의 종료 조건
- 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다.
- 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다.
- 종료 조건을 포함한 재귀 함수 예제
function recursiveFunction(count) {
if (count <= 0) { // 종료 조건
console.log('재귀 호출을 멈춥니다.');
return;
} else {
console.log(count);
recursiveFunction(count - 1); // 자기 자신을 호출
}
}
recursiveFunction(5);
팩토리얼 구현 예제
- n! = 1 x 2 x 3 x... x (n - 1) x n
- 수학적으로 0! 과 1! 의 값은 1이다.
function factorial(n) {
if (n === 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
console.log(factorial(5)); // 출력 결과: 120if else 문에서 리턴값의 계산 방식이 이해가 잘 안 돼서 GPT한테 물어봤다..
factorial(1) 함수에서 1을 반환하면, 이 값이 factorial(2) 함수로 전달된다.
그리고 factorial(2) 함수에서는 n이 2일 때, factorial(1) 함수를 호출하게 되어 1을 반환한다.
그러면 factorial(2) 함수에서는 반환된 1과 n을 곱한 2 * 1의 값을 반환하게 된다.
따라서 factorial(5) 함수를 호출한 결과는 다음과 같다.
- factorial(5) 함수가 호출됨
- n === 5 이므로 factorial(4) 함수를 호출
- n === 4 이므로 factorial(3) 함수를 호출
- n === 3 이므로 factorial(2) 함수를 호출
- n === 2 이므로 factorial(1) 함수를 호출
- factorial(1) 함수가 1을 반환하고, 이 값이 factorial(2) 함수로 전달됨
- factorial(2) 함수에서 반환된 1과 n(2)를 곱한 2를 반환함
- factorial(3) 함수에서 반환된 2와 n(3)을 곱한 6을 반환함
- factorial(4) 함수에서 반환된 6과 n(4)을 곱한 24를 반환함
- factorial(5) 함수에서 반환된 24와 n(5)를 곱한 120을 반환함
호출된 함수들이 스택 구조에 쌓이게 되고, 함수 호출이 끝나면 가장 마지막에 호출된 함수가 반환되면서, 결과적으로 입력된 인수의 팩토리얼 값이 반환된다.
최대공약수 계산 (유클리드 호제법) 예제
- 두개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘으로 유클리드 호제법이 있다.
- 유클리드 호제법
- 두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지를 R.
- 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다.
- 유클리드 호제법의 아이디어를 그대로 재귀 함수로 작성 가능.
- 예시: GCD(192, 162) // GCD === 최대공약수
| 단계 | A | B |
| 1 | 192 | 162 |
| 2 | 162 | 30 |
| 3 | 30 | 12 |
| 4 | 12 | 6 |
function gcd(a, b) {
if (a % b === 0) {
return b;
} else {
return gcd(b, a % b);
}
}
gcd(192, 162);재귀 함수 사용의 유의 사항
- 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성 가능.
- 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있음.
- 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현 가능.
- 재귀 함수가 반복문보다 유리한 경우, 불리한 경우 둘 다 있음.
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임.
- 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많음.
