재귀함수가 뭔가요? (Feat. 하노이의 탑)
직접 구현하기는 물론 작성된 코드를 읽기도 머리아픈 재귀함수.
무엇에 쓰는 함수이고 왜 사용되며, 또 위험성은 어떤 것이 있는지
그리고 함께 배우곤 하는 '꼬리재귀'란 어떤 개념인지 배워봅시다.
또한 많은 컴공 학생들의 두통을 유발하는 🗼하노이의 탑도
최대한 쉽게 이해할 수 있도록 설명해봤어요.
한 번에 알아듣진 못하더라도, 🧐 몇 번 반복해서 듣다 보면
하노이의 탑의 원리를 파악하실 수 있을거에요.
| 목차 | 분:초 |
|---|---|
| 재귀함수가 뭔가요? | 00:00 |
| 하노이의 탑 설명 | 03:35 |
⌨️ 코드 예제 Javascript
∑ 배열 총합 예제
코드
let numbers = [3, 1, 4, 1, 5, 9];
function recursive(acc, array) {
if (array.length === 0) {
console.log(`총합은 ${acc}`);
return acc;
} else {
try {
console.log(`recursive(${acc} [${array}])가 "`)
return recursive(acc + array[0], array.slice(1));
} catch (e) {} finally {
console.log('"이라고 말했어요.');
}
}
}
recursive(0, numbers)
결과
recursive(0 [3,1,4,1,5,9])가 "
recursive(3 [1,4,1,5,9])가 "
recursive(4 [4,1,5,9])가 "
recursive(8 [1,5,9])가 "
recursive(9 [5,9])가 "
recursive(14 [9])가 "
총합은 23
"이라고 말했어요.
"이라고 말했어요.
"이라고 말했어요.
"이라고 말했어요.
"이라고 말했어요.
"이라고 말했어요.
🐍 꼬리 재귀
아래와 같이 return 값이 함수 실행 그 자체여야 함
function canTailRecurse (arg) {
// ...
return canTailRecurse(arg);
}
🗼하노이의 탑
function hanoi (num, from, to, other) {
// num: 원반의 수
// from: 원반들이 위치한 곳의 번호
// to: 원반들을 옮길 목적지 번호
// other: 나머지 한 곳(목적지가 아닌) 곳 번호
// 모두 옮겼으면 종료
if (num === 0) return;
// 가장 아래 원반을 제외한 원반들을 재귀적으로 목적지가 아닌 곳으로 옮김
hanoi(num - 1, from, other, to);
// 가장 아래 원반을 목적지로 옮김
console.log(`${from}번에서 ${to}로 옮긴다.`);
// 목적지가 아닌 곳으로 옮겼던 원반들을 재귀적으로 목적지로 옮김
hanoi(num - 1, other, to, from);
}
hanoi(4, 0, 1, 2);
실행 결과
0번에서 2로 옮긴다.
0번에서 1로 옮긴다.
2번에서 1로 옮긴다.
0번에서 2로 옮긴다.
1번에서 0로 옮긴다.
1번에서 2로 옮긴다.
0번에서 2로 옮긴다.
0번에서 1로 옮긴다.
2번에서 1로 옮긴다.
2번에서 0로 옮긴다.
1번에서 0로 옮긴다.
2번에서 1로 옮긴다.
0번에서 2로 옮긴다.
0번에서 1로 옮긴다.
2번에서 1로 옮긴다.
🍿 더 자세한 내용은 영상에서 보실 수 있습니다.
유튜브에서 영상 보기