- 재귀란
자기 자신을 참조하는 것.
국어사전에는 '원래 자리로 되돌아가거나 되돌아옴' 이라고 쓰여져 있다.
더 와닿게 설명하자면
모르는 영어단어를 발견해서 영영사전을 봤는데, 그 사전에 있는 설명에도 모르는 영어단어가 있어서 그 영어단어를 찾아보고, 근데 그거에 대한 설명에도 모르는 영어단어가 있어서 또 찾으러 가는... 이런 상황을 이야기한다.
- 장단점
2-1. 장점 : 가독성이 좋다. 이중 for 문을 사용하는 것보다 재귀함수로 표현하는 것이 편하다.
2-2. 단점 : 값이 리턴되기 전까지 호출마다 call stack 을 형성해서 메모리를 많이 사용한다.
- 재귀함수 예시
factorial 로 재귀함수를 처음 배웠는데, 감명받았었다.
(팩토리얼이란 하나의 자연수를 받았을때, 1부터 해당 자연수까지의 모든 수를 곱셈한 것을 말한다.)
factorial(1) = 1
factorial(2) = 1 * 2 = 2
factorial(3) = 1 2 3 = 6
factorial(4) = 1 2 3 * 4 = 24
이렇게 되는 함수를 만들어 보겠다.
1) 재귀의 기초, 즉 base case 를 먼저 설정해야한다.
가장 작은 경우의 리턴 값을 정하는 것이다. 이 부분에 도달하면 재귀는 멈추게 된다. (앞서 말했던 영영사전 예시에서 더이상 찾을 영어단어가 없을 때, 우리는 그 전에 찾았던 단어로 되돌아 오게 되는 것처럼)
function factorial(num) {
// 재귀의 기초 (base case)
if (num === 0) {
return 1;
}
}0! 은 1이기 때문에, factorial 함수에 0이 들어오면 1로 리턴하게 설정했다.
2) 재귀의 기초가 아닌 경우, 즉 recursive case (반복되는 경우) 를 설정해보겠다.
factorial 함수에 1이 들어온 경우를 생각해보겠다.
리턴 값에는 해당 수인 1을 남겨두고, 1에서 1을 뺀 0을 다시 factorial 함수에 넣는다.
앞서 factorial(0) 은 1을 리턴하니까
결국 1 * 1 = 1 이 된다.
function factorial(num) {
// 재귀의 기초 (base case)
if (num === 0) {
return 1;
}
// recursive Case
return num * factorial(num-1)
}3) 이번엔 5를 넣어서 과정을 살펴보겠다.
factorial(5) // 이 부분을 쓰고 엔터를 누르면
//아래의 과정이 진행된다.
// 1번째 호출
function factorial(5) {
// recursive Case
return 5 * factorial(4)
}
// 2번째 호출
function factorial(4) {
// recursive Case
return 4 * factorial(3)
}
// 3번째 호출
function factorial(3) {
// recursive Case
return 3 * factorial(2)
}
// 4번째 호출
function factorial(2) {
// recursive Case
return 2 * factorial(1)
}
// 5번째 호출
function factorial(1) {
// recursive Case
return 1 * factorial(0)
}
// 6번째 호출
function factorial(0) {
// 재귀의 기초 (base case)
if (0 === 0) {
return 1;
}
}이렇게 6개의 call stack 이 쌓인걸 확인할 수 있다.
call stack 은 값을 리턴하면 사라진다.
하지만 리턴하기 전까지 계속 쌓이며 메모리를 소모하므로 주의해서 사용해야 한다.
4. 재귀함수 주의해야 할 점 🌟🌟
재귀함수 문제를 풀면서 헷갈렸던 부분에 대해 정리해봤다.
let input = [1, [2 ,[3]], [[4], 5] ]
// 이런 형식으로 생긴 배열에서 숫자찾기 놀이를 해보겠다.
function picknum(arr, num) {
// 여기에 코드를 작성할 것이다.
}
//예시
console.log(picknum(input, 1)) // 1이 출력되게 만들것이다.1) 값을 찾으면 바로 리턴되게 함수를 작성해봤다. (잘못된 코드)
let input = [1, [2 ,[3]], [[4], 5] ]
function picknum(arr, num) {
for (let i = 0; i < arr.length; i ++) {
// 1. 만약 num 을 찾으면 바로 리턴
if(arr[i] === num) {
return arr[i];
}
// 2. 배열요소타입이 배열이면 한번더 재귀함수 호출
else if (Array.isArray(arr[i])) {
return picknum(arr[i], num)
}
}
// 3. 찾는값이 없으면 null 로 리턴하게 만듬
return null;
}
// 결과
console.log(picknum(input, 1)) // 1
console.log(picknum(input, 2)) // 2
console.log(picknum(input, 3)) // 3
console.log(picknum(input, 4)) // null
console.log(picknum(input, 5)) // null그런데 이런.. 숫자 4와 5가 null 로 출력된다.
값을 직접하나하나 살펴보면서 확인해보자.
console.log(picknum(input, num)) // num에 4를 넣은 경우를 살펴보자.
// 1번째 호출
// 1. arr[i] 가 1 인 경우
function picknum([1, [2 ,[3]], [[4], 5] ], 4) {
for (let i = 0; i < arr.length; i ++) {
if(arr[i] === num) { // 1 !== 4 이니까 패스
return arr[i];
}
else if (Array.isArray(arr[i])) { // 1 은 배열이 아니니까 재귀함수 호출이 안됨
return picknum(arr[i], num)
}
}
return null;
}
// 2. arr[i] 가 [2 ,[3]] 인 경우
function picknum([1, [2 ,[3]], [[4], 5] ], 4) {
for (let i = 0; i < arr.length; i ++) {
if(arr[i] === num) { // [2 ,[3]] !== 4 이니까 패스
return arr[i];
}
else if (Array.isArray([2 ,[3]])) { // 배열이 맞으니까 재귀함수가 호출됨
return picknum([2 ,[3]], 4)
}
}
return null;
}
// 2번째 호출
// 1. arr[i] 가 2 인 경우
function picknum([[2 ,[3]], 4) {
for (let i = 0; i < arr.length; i ++) {
if(arr[i] === num) { // 2 !== 4 이니까 패스
return arr[i];
}
else if (Array.isArray(arr[i])) { // 2 는 배열이 아니니까 재귀함수 호출이 안됨
return picknum(arr[i], num)
}
}
return null;
}
// 2. arr[i] 가 [3] 인 경우
function picknum([[2 ,[3]], 4) {
for (let i = 0; i < arr.length; i ++) {
if(arr[i] === num) { // [3] !== 4 이니까 패스
return arr[i];
}
else if (Array.isArray([3])) { // 배열이 맞으니까 재귀함수가 호출됨
return picknum([3], 4)
}
}
return null;
}
// 3번째 호출
function picknum([3], 4) {
for (let i = 0; i < arr.length; i ++) {
if(arr[i] === num) { // 3 !== 4 이니까 패스
return arr[i];
}
else if (Array.isArray(arr[i])) { // 3 은 배열이 아니니까 재귀함수 호출이 안됨
return picknum(arr[i], num)
}
}
// for문이 끝나버려서 null 로 리턴
return null;
}
console.log(picknum(input, 4)) // null결론 : 4를 찾아내기도 전에 코드가 끝나버린다.
2) 입력받은 배열 속 모든 요소를 조회할 수 있도록 코드를 작성해야 한다.
힌트를 주자면, 나는 else if 문에서 재귀함수를 호출할 때 바로 리턴되는 것이아니라,
재귀함수 값을 변수에 할당해서 4, 5 모두 조회할 수 있게 만들었다.
- 느낀점
나는 for 문을 좋아하는데, 이와 비슷한 재귀함수도 좋아하게 되었다.
이중포문 작성 진짜 자신있다 ! ㅎㅎ
다양한 문제들을 풀면서 입력값의 경우의 수에 대해 생각하게 되었고
앞으로 입력값의 모든 경우의 수를 지배하는 자가 되고 싶다 !!
사실 이 포스팅은 거의 3일이 걸려서 작성한 글이다.
분명 풀어낸 문제인데, 막상 글을 쓰면서 설명을 하려니 힘들었다.
재귀함수를 처음 접하는 분들께도 이해할 수 있게 글을 작성하고 싶었다..
내 의도가 잘 실현됐을지 모르겠다 ㅎㅎ
(혹시 글에서 부족한 부분이나 궁금한 점이 있으면 언제든 댓글 바랍니다!)
