재귀 함수
원하는 값에 도달 할 때 까지 자기 자신을 호출하는 함수이다.
예시1 팩토리얼(재귀 함수로 표현O)
function fact(num) {
//입력받은 값과 그 값에 -1한 값을 재귀적으로 호출
return num <= 1 ? 1 : num * fact(num-1);
}
console.log(fact(10)); //3628800예시1 팩토리얼(재귀 함수로 표현X)
function fact(num) {
let result = 1;
//입력받은 값에서 1까지 내려가면서 곱함
for(let i = num; i>=1; i--){
result*=i;
}
return result;
}
console.log(fact(10)); //3628800예시2 피보나치(재귀 함수로 표현 O)
function fibo(num) {
return num <= 2 ? 1 : fibo(num-1) + fibo(num-2)
}
console.log(fibo(10)); //55예시2 피보나치(재귀 함수로 표현 X)
function fibo(num) {
if(num == 0) return 0;
if(nmm <= 2) return 1;
let result = 1;
let prev = 1;
for(let i = 3; i <= num; i++){
let temp = result + prev;
prev = result;
result = temp;
}
return result;
}
console.log(fibo(10)); //55첫 번째 예시에서 재귀 함수를 쓴 것과 안 쓴 코드의 작동 방식은 거의 동일하다. 똑같이 반복 적으로
주어진 숫자에서 1까지 내려가면서 계산한다.
두 번째 예시에서는 조금 다르다. 반복문으로 구현한 코드에서는 이전에 계산한 값들을 저장해서 다음 값을 계산한다.
재귀 함수로 구현한 코드들이 더 간결하고 가독성도 더 좋다.
하지만 재귀 함수로 구현한 코드에서는 각 피보나치의 값들을 끝까지 내려가서 계산을 해온다. 즉 반복문이 훨씬 효율적이고 빠르다.
물론 동적 계획 법으로 재귀 함수의 보완이 가능 하다.
위 두 가지의 예시들은 모두 원하는 값을 계산하기 위해 재귀 적으로 호출된다.
다음에 보여줄 예시는 원하는 값이 아니라 특정 배열을 완성 시키기 위한 재귀 함수이다.
예시3 이진 탐색(재귀적 표현 O)
let arr = [3,10,6,14,8,13,1,4,7] //정렬되지 않은 배열
function setBinaryTree(arr) {
let BT = []; //BT(BinaryTree)
BT[1] = arr[Math.floor(arr.length/2)];
this.sort = function (start = 0,node = 1) {
console.log(`start = ${start}, node = ${node}`)
//정렬하고자 하는 start인덱스의 arr값이 존재하지 않다면 == arr의 끝까지 돌았다면
if(arr[start] == undefined) return;
//정렬할 arr의 start번째 인덱스의 값이 BT[node]보다 작으면 == 왼쪽 자식노드
if(arr[start] < BT[node]) {
//BT의 왼쪽 자식노드가 비어있으면 arr[start]를 넣어주고 arr의 다음 인덱스와 다시 BT의 1번째 노드로 돌아감
BT[node*2] == undefined
? (BT[node*2] = arr[start],this.sort(start+1, 1))
//BT의 왼쪽 자식노드가 비어있지 않다면 node*2의 값으로 다시 this.sort호출
: BT[node*2] != undefined
? this.sort(start, node*2)
: undefined;
//정렬할 arr의 start번째 인덱스의 값이 BT[node]보다 크면 == 오른쪽 자식노드
} else if (arr[start] > BT[node]) {
//BT의 오른쪽 자식노드가 비어있으면 arr[start]를 넣어주고 arr의 다음 인덱스와 다시 BT의 1번째 노드로 돌아감
BT[node*2+1] == undefined
? (BT[node*2+1] = arr[start],this.sort(start+1, 1))
//BT의 오른쪽 자식노드가 비어있지 않다면 node*2+1의 값으로 다시 this.sort호출
: BT[node*2+1] != undefined
? this.sort(start, node*2+1)
: undefined;
} else {
this.sort(start+1, node)
}
}
this.show = function () {
return BT;
}
}
let Tree = new setBinaryTree(arr);
Tree.sort();
console.log(Tree.show());위 코드는 이진 탐색 알고리즘에서 배열에 대해서 정렬 할 때 재귀적으로 정렬을 한 것이다.
- 더 자세한 이진 탐색 알고리즘 및 반복문으로의 구현 이진 탐색은 우리가 배열에서 특정한 값을 빠르게 찾고자 할 때 사용하는 알고리즘이다. 자바스크립트에서
특정한 값의 인덱스를 모른다고 했을 때 그특정한 값을 찾기 위해서 일반 for문즉 선형적 탐색을 사용할 경우O(n)만큼의 시간이 걸린다. 여기서 n은 배열의 길이 만큼이다. 최악의 경우 찾고자 하는 값이 배열의 맨 끝에 존재할 경우 배열의 길이만큼 시간이 걸린다. 이진 탐색은 특정한 값을 기준root로 특정한 값보다 작으면 왼쪽 자식 노드, 특정한 값보다 크면 오른쪽 자식 노드로 형성된 이진 트리에서 값을 찾는데 걸리는 시간은 최악의 경우에도O(log n)이 걸린다. 아래의 그림을 보면 이해가 쉽다.
위 그림은 8을 루트로8보다 작은3은 왼쪽10은 오른쪽 자식으로 지정하고 다시 그3과10에서 다시 본인보다 작으면 왼쪽 자식, 크면 오른쪽 자식으로 분류하고 있다. 위 그림을 배열로 만들 수 있다.
위 배열에서 0번째 인덱스는let Binary_tree = [null ,8 ,3 ,10 ,1 ,6 ,null ,14 ,null ,null ,4 ,7 ,null null 13] //[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14] <- 배열의 인덱스 //여기서 root는 1번째 인덱스 8null로 취급 해 줬다. 그 이유는 우리가 자식 노드를 정할 때 부모 노드의 index 를 기준으로 왼쪽 자식 노드, 오른쪽 자식 노드를 정할 때 0부터 계산하면 귀찮기 때문이다. 부모 노드의 인덱스를i라 할 때(i x 2)는 왼쪽 자식 노드(i x 2) + 1은 오른쪽 자식 노드 이다. 보통root는 arr[Math.floor(arr.length/2)]즉 배열의 중간 인덱스로 정한다. 위와 같이 이진 트리로 만든 후특정한 값을 찾고자 할 때root부터 찾고자 하는특정한 값과 비교해 나간다.찾고자 하는 값 = 6라 할 때 처음부터8과 비교해서8보다 작으니 왼쪽 자식 노드3과 비교하고3보다 크니3의 오른쪽 자식인6이렇게 값을 찾는다. 이진 탐색(Binary Search) 자바스크립트로 구현
삭제 기능은 넣지 못했다. 삭제할 녀석의 자식 노드가 없는 경우에는 그것만 제외하면 정말 간단하지만, 자식 노드가 하나 일 경우, 두 개 일 경우, 그 자식의 자식 노드가 또 한 개 일 경우 등.. 너무 복잡해질 것 같아서 이 정도만 구현 했습니다. 위에 코드를 보면 쓸데없이 길고 그냥 선형적으로 for문으로 탐색하면 안되나 싶겠지만, 데이터 양이 많아 질때 효율적인 서치를 위해 이진탐색알고리즘을 사용하는 것이 좋습니다. 예시로는 "주소록에서 특정 이름을 찾기"입니다. 예를 들어, 사용자가 주소록에 등록된 사람의 이름을 검색하고자 할 때, 이진 탐색은 효율적인 검색 방법으로 사용될 수 있습니다. 주소록은 일반적으로 알파벳순으로 정렬되어 있으며, 이진 탐색을 사용하여 특정 이름을 빠르게 찾을 수 있습니다. 이진 탐색은 중간 위치의 이름과 찾고자 하는 이름을 비교하여 찾고자 하는 이름이 위치한 범위를 좁혀가며 탐색을 수행합니다. 이렇게 반복하여 이름을 찾을 때까지 탐색을 진행하면 효율적으로 결과를 얻을 수 있습니다. 위 코드가 어떻게 작동하는지 직접 눈으로 보고 싶으면 아래의 사이트를 참고해주시면 됩니다. https://visualgo.net/en/bstlet arr = [3,10,6,14,8,13,1,4,7] //정렬되지 않은 배열 function MakeBinaryTree(arr) { let BT = []; //BT(BinaryTree) BT[1] = arr[Math.floor(arr.length/2)]; this.sort = function () { for(let i = 0 ; i < arr.length; i++){ let node = 1; //root부터 비교하기시작 while(1) { if(arr[i] > BT[node] && BT[node*2+1] == undefined) { BT[node*2+1] = arr[i] break; } else if (arr[i] < BT[node] && BT[node*2] == undefined) { BT[node*2] = arr[i]; break; } else if (arr[i] > BT[node] && BT[node*2+1] != undefined){ node = node*2 + 1 } else if (arr[i] < BT[node] && BT[node*2] != undefined) { node = node*2; } else { break; } } } } this.insert = function (num) { let node = 1; while(1) { if(num > BT[node] && BT[node*2+1] == undefined) { BT[node*2+1] = num break; } else if (num < BT[node] && BT[node*2] == undefined) { BT[node*2] = num break; } else if (num > BT[node] && BT[node*2+1] != undefined){ node = node*2 + 1 } else if (num < BT[node] && BT[node*2] != undefined) { node = node*2; } else { break; } } } this.findvalue = function (num) { let node = 1; while(node < BT.length) { if(num < BT[node] && BT[node] != undefined) { node = node*2; } else if(num > BT[node] && BT[node] != undefined) { node = node*2+1; } else { break; } } if(BT[node] == num) { return 1; } else { return 0; } } this.show = function () { console.log(BT); } } let new_arr = new MakeBinaryTree(arr); new_arr.sort(); //arr를 이진트리로 새롭게 정렬 console.log(new_arr.findvalue(13)) //1출력 console.log(new_arr.findvalue(1)) //1출력 console.log(new_arr.findvalue(5)) //0출력 console.log(new_arr.insert(5)); //5를 넣고 재정렬 console.log(new_arr.findvalue(5)) //1출력 console.log(new_arr.show()) //[undefiend ,8 ,3 ,10 ,1 ,6 ,undefined ,14 ,undefined * 2 ,4 ,7 ,undefined * 2 ,13 ,undefined * 6, 5];
이진 탐색, 우선순위 큐와 같은 이진 트리 형태의 배열을 가지는 알고리즘에 대해서는 재귀 함수를 사용할 수 있다.
재귀 함수를 사용함에 따라 가독성이 일반 반복문 보다 뛰어날 수 있다.
재귀 함수는 코드를 간결하게 짤 수 있고, 가독성이 좋다는 장점이 있지만 문제에 따라 함수의 수많은 호출과 그로 인해 발생하는 stack over flow 와 같은 문제점이 발생할 수 있다.
따라서 재귀 함수가 무조건 좋은 것이 아니고 일반 반복문이 더 빠르고 상황에 따라서는 가독성도 일반 반복문이 좋을 수 있다.
백엔드 개발자를 희망하는