알고리즘 01 재귀함수 기본 | 팩토리얼, 거듭제곱, 피보나치, GCD(최대공약수), 이진탐색) 외 | JS
1. What is Recursion?
재귀란 무엇인가
- 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식
이미지 출처
재귀함수: 무한루프
function recursion() {
console.log("here");
recursion();
}
recursion() // 무한 루프
재귀함수: 무한루프 개선
function recursion(count) {
if (count < 0) return // 반복을 멈출 조건을 설정
console.log("here", count);
recursion(count - 1); // 인수 업데이트 및 재귀 함수 호출
}
let count = 4;
recursion(count)
- 개념적으로 다시보기
function recursion(count) {
if (count < 0) return // base case
// 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 함
console.log("here", count);
recursion(count - 1); // Recursive case
// recursion을 반복하다보면 결국 base case로 수렴해야 함.
}
let count = 4;
recursion(count)
- 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 함
- recursion을 반복하다보면 결국 base case로 수렴해야 함
1~n
까지의 합 구하기
// 이 함수의 mission은 0~n까지의 합을 구하는 것
function recursion(num) {
if (num === 0) {
// n=0이라면 합은 0
return 0
} else {
// n이 0보다 크다면 0에서 n까지의 합은 0에서 n-1까지의 합에 n을 더한 값
return num + recursion(num - 1);
}
}
let num = 4;
recursion(num)
팩토리얼(Factorial: n!)
- 0! = 1
- n! = n*(n-1)! (n>0)
function factorial(n) {
if (n === 0) {
return 1
} else {
return n * factorial(n - 1)
}
}
let n = 4;
factorial(n)
거듭제곱
- num^0 = 1
- num^n = n * n^n-1 (n > 0)
function power(num, n) {
if (n === 0) {
return 1
} else {
return num * power(num, n - 1)
}
}
const num = 2
const n = 4;
power(num, n)
피보나치
- f(0) = 0
- f(1) = 1
- f(n) = f(n-1) + f(n-2) (n>1)
function fibonacci(n) {
if (n < 2) {
return n
} else {
return fibonacci(n - 1) + fibonacci(n - 2)
}
}
const n = 4;
fibonacci(n)
최대공약수 | GCD
- Greatest Common Divisor: Euclid Method
- 앞의 수가 더 커야만 성립하기 때문에 검사 후 자리를 바꿔주는 로직 필요
function gcd(a, b) {
if (a < b) {
let temp = a
a = b
b = temp
}
if (a % b === 0) {
return b
} else {
return gcd(b, a % b)
}
}
const a = 12;
const b = 8;
gcd(a, b)
최대공약수 개선
- 두 수의 대소 관계가 무관하도록 개선
function gcd(a, b) {
if (b === 0) {
return a
} else {
return gcd(b, a % b)
}
}
const a = 8;
const b = 12;
gcd(a, b)
2. Recursive Thinking
순환적으로 사고하기
문자열의 길이 계산
function strLength(str) {
if (!str) {
return 0
} else {
return 1 + strLength(str.substring(1))
}
}
const str = "Hello world!"
strLength(str)
문자열의 프린트
function printChars(str) {
if (!str) {
return;
} else {
console.log(str.charAt(0))
printChars(str.substring(1))
}
}
const str = "Hello world!"
printChars(str)
문자열을 뒤집어 프린트
function printCharsReverse(str) {
if (!str) {
return;
} else {
printCharsReverse(str.substring(1))
console.log(str.charAt())
}
}
const str = "Hello world!"
printCharsReverse(str)
2진수로 변환하여 출력
function printInBinary(n) {
if (n < 2) {
console.log(n);
} else {
printInBinary(Math.floor(n / 2))
console.log(n % 2);
}
}
const n = 10;
printInBinary(n)
배열의 합 구하기
- data[0]에서 data[n-1]까지의 합을 구하여 반환
function arraySum(n, arr) {
if (n <= 0) {
return 0;
} else {
console.log(arr[n - 1]);
return arr[n - 1] + arraySum(n - 1, arr)
}
}
const n = 10;
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
arraySum(n, arr);
Recursion Vs Iteration
재귀 vs 반복
- 모든 순환함수는 반복문으로 변경 가능
- 그 역도 성립함. 즉 모든 반복문은 recursion으로 표현 가능
- 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 함
- 하지만 함수 호출에 따른 오버헤드가 있음(매개변수 전달, 액티베이션 프레임 생성 등)
- 함수가 중첩되어 호출되면 계속해서 메모리에 쌓여 stack overflow가 발생할 수 있음
- 성능면에서 뒤쳐질 수 있지만, 반복을 사용하면 굉장히 복잡할 수 있는 로직을 재귀로 단순화 할 수 있기 때문에 활용도가 높음
3. Designing Recursion
순환 알고리즘의 설계
무한루프에 빠지지 않는 재귀함수의 전제 조건
- 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 함
- recursion을 반복하다보면 결국 base case로 수렴해야 함
재귀함수 디자인
암시적(implicit) 매개변수를
명시적(explicit) 매개변수로 바꾸어라.
순차탐색
순차 탐색(반복) | Sequential search
- 이 함수의 mission은 data[0]에서 data[n-1]사이에서 target을 검색하는 것이다.
- 하지만 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉 암시적 매개변수이다.
ex)
[0, n-1] => 0에서부터 n-1까지
0 => 암시적
n-1 => 명시적
function search(arr, n, target) {
for (let i = 0; i < n; i++) {
if (arr[i] === target) {
return i
}
}
return -1
}
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
const n = 7
const target = 5
console.log(search(arr, n, target));
순차 탐색(재귀) | Sequential search
- 매개변수의 명시화
- 반복을 통한 순차 탐색에서 암시적 매개변수였던 시작점을 명시적으로 변경
ex) 0 => start
function search(arr, begin, end, target) {
if (begin > end) {
return -1;
} else if (target === arr[begin]) {
return begin
} else {
return search(arr, begin + 1, end, target)
}
}
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
const begin = 0
const end = 7
const target = 5
console.log(search(arr, begin, end, target))
- 이 함수를 search(data, 0, n-1, target)으로 호출한다면
반복문을 활용한 함수와 완전히 동일한 일을 함즉, 재귀함수를 구현할 때 처음 함수를 실행하는 경우뿐만 아니라 두번째, 세번째 실행할 때의 매개변수를 염두해두고 설계를 해야함
순차 탐색(재귀) v2
function search(arr, begin, end, target) {
if (begin > end) {
return -1;
} else if (target === arr[end]) {
return end
} else {
return search(arr, begin, end - 1, target)
}
}
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
const begin = 0
const end = 7
const target = 5
console.log(search(arr, begin, end, target));
순차 탐색(재귀) v3
function search(arr, begin, end, target) {
if (begin > end) {
return -1;
} else {
let mid = Math.floor((begin + end) / 2)
if (arr[mid] === target) {
return mid
}
let index = search(arr, begin, mid - 1, target)
if (index !== -1) {
return index
} else {
return search(arr, mid + 1, end, target)
}
}
}
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
const begin = 0
const end = 7
const target = 5
console.log(search(arr, begin, end, target));
최대값 찾기
최대값 찾기(반복)
function findMax(arr) {
let max = 0;
for (let i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i]
}
}
return max
}
const arr = [1, 2, 5, 6, 4, 7, 9, 8, 3]
console.log(findMax(arr));
최대값 찾기(재귀)
- 반복문으로 구현한 최대값 찾기에서 암시적으로 표현한 0을 명시적으로 표현
ex) 0 => index
function findMax(index, arr) {
if (index === arr.length-1) {
return arr[index]
} else {
return Math.max(arr[index], findMax(index + 1, arr))
}
}
const arr = [1, 2, 5, 6, 4, 7, 9, 8, 3]
console.log(searchMaxValue(0, arr));
최대값 찾기(재귀) v2
function findMax(begin, end, arr) {
if (begin === end) {
return arr[begin]
} else {
let mid = Math.floor((begin + end) / 2)
let max1 = findMax(begin, mid, arr)
let max2 = findMax(mid + 1, end, arr)
return Math.max(max1, max2)
}
}
const arr = [1, 2, 5, 6, 4, 7, 9, 8, 3]
const end = arr.length - 1
console.log(findMax(0, end, arr));
이진 탐색 | Binary Search
- 조건 : 데이터가 크기 순으로 정렬되어 있음을 전제로 함
- arr[begin] ~ arr[end] 사이에서 target을 검색해서 index를 반환
function binarySearch(arr, target, begin, end) {
if (begin > end) {
return -1
} else {
let mid = Math.floor((begin + end) / 2)
if (arr[mid] === target) {
return mid
} else if (arr[mid] > target) {
return binarySearch(arr, target, begin, mid - 1)
} else {
return binarySearch(arr, target, mid + 1, end)
}
}
}
//if arr가 정렬되어 있지 않다면, arr.sort() 필요
const arr = [1, 2, 4, 9, 13, 15, 20, 22, 30, 40, 50, 60, 77, 100];
const target = 77;
const begin = 0;
const end = arr.length - 1;
console.log(binarySearch(arr, target, begin, end));
📚 참고
YOUTUBE | 2015 봄학기 알고리즘 | 권오흠
모던 JavaScript 튜토리얼 | 재귀와 스택
Photo by Michael Dziedzic on Unsplash
Author And Source
이 문제에 관하여(알고리즘 01 재귀함수 기본 | 팩토리얼, 거듭제곱, 피보나치, GCD(최대공약수), 이진탐색) 외 | JS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@protect-me/알고리즘-01-재귀함수-JS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)