개요
자기 자신을 호출하는 함수 (재귀함수)
function recur () {
recur();
}
// 무한 루프에 빠짐.
// 종료할 조건이 필요하다!
function logHello (count) {
if (count <= 0 return;
console.log('Hello')
logHello(count - 1);
}
JavaScript
복사
1.
적어도 하나의 recursion 에 빠지지 않는 경우가 존재해야함
2.
recursion 을 반복하다보면 결국 base case 로 수렴해야한다
3.
암시적(implicit) 매개변수(explicit)를 명시적 매개변수로 바꾸어라
순환적으로 사고하기
1.
모든 순환함수는 반복문(iteration) 으로 변경 가능
2.
그 역도 성릭함
3.
순환함수는 복잡한 알고리즘을 알기 쉽게 표현하는 것을 가능하게 함
4.
하지만 함수 호출에 따른 오버해드가 있음 (매개변수 전달, 액티베이션 프레임(?) 생성 등)
함수들
factorial
function factorial (n) {
if (n <= 0) return 1;
return n * factorial(n - 1);
}
JavaScript
복사
fibonacci
function fibonacci (n) {
if (n < 2) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
JavaScript
복사
euclid (최대 공약수)
function gcd (m, n) {
if (m < n) {
var temp = m;
m = n;
n = temp;
}
if (m % n === 0) return n;
return gcd(n, m % n);
}
JavaScript
복사
sum
// 숫자 배열의 합을 구하는 함수
function sum (n, list) {
if (n <= 0) return 0;
return sum(n -1, list) + data[n - 1]
}
JavaScript
복사
search
function search (list, target) {
for(var i = 0; i < list.length; i++) {
if (data[i] == target) return i;
}
return -1;
}
// startIndex = 0, endIndex = list.length -1
// 일 것이라고 생각함. 암시적인 선언이다. 아래와 같이 명시적으로 하는 것이 좋다
// 수정본
function search (list, begin, end, target) {
if (begin > end) return -1;
else if (target == list[begin]) return begin;
else return search(list, begin + 1, end, target);
}
// 시작 (begin) 과 끝(end ) 를 명시적으로 표시한다
// 다른 버젼. 중간에서 시작한다.
function search (list, begin, end, target) {
if (begin > end) return -1;
var middle = (begin + end) / 2;
if (list[middle] === target) return middle;
var index = search = search(list, begin, middle - 1, target)'
if (index != -1) return index;
return search(list, middle + 1, end, target);
}
JavaScript
복사
findMax
function findMax (list, begin, end) {
if (begin === end) return data[begin];
return Math.max(list[begin], findMax(list, begin + 1, end));
}
JavaScript
복사
binarySearch
// 기본적으로 주어진 데이터가 정렬 되어있을 거라는 전제
function binarySearch (list, target, begin, end) {
if (begin > end) return -1;
var middle = (begin + end) / 2;
if (target === list[middle]) return middle;
if (target < list[middle]) return binarySearch(list, target, begin, middle - 1);
return binarySearch(list, target, middle + 1, end);
}
JavaScript
복사
permutation(순열알고리즘)
// 가능한 모든 배열의 경우를 리턴하는 함수
function permutation(list, start, end)
{
if (start == end)
{
for (const auto it : Array)
{
cout << it << " ";
}
cout << endl;
}
else
{
for (var i = start; i <= end; ++i)
{
swap(list[start], list[i]);
Permutation(list, start + 1, end);
swap(list[start], list[i]);
}
}
}
// 참고 - https://minusi.tistory.com/m/entry/%EC%88%9C%EC%97%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Permutation-Algorithm
function permu(a) {
return a.reduce(
function(list, element) {
var newlist = [];
list.forEach(function(seq) {
for (var i = seq.length; i >= 0; i--) {
var newseq = [].concat(seq);
newseq.splice(i, 0, element);
newlist.push(newseq);
}
});
return newlist;
},
[[]]
);
}
var list = [1, 2, 3];
permu(a);
// [[1]] =>
// [[2, 1], [1, 2]] =>
// [[3, 2, 1], [2, 3, 1], [2, 1, 3], ...]
JavaScript
복사
미로찾기
현재 위치에서 출구까지 가는 경로가 있으려면
1. 현재 위치가 출구이거나
2. 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나
function findPath (x, y) {
if (isExit(x, y)) return true;
markVisitedPath(x, y);
_x, _y = neighbouring path;
if (isOnTheWay(_x, _y)) return findPath(_x, _y);
return false;
}
=>
function findPath (x, y) {
if (isWall(x, y) || isVisited(x, y)) return false
if (isExit(x, y)) return true;
markVisitedPath(x, y);
_x, _y = neighbouring path;
return findPath(_x, _y);
return false;
}
JavaScript
복사
// 실 문제
var PATHWAY_COLOR = 0;
var WALL_COLOR = 1;
var BLOCKED_COLOR = 2;
var PATH_COLOR = 3;
var N = 8;
var LOADS = [
[0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 1, 1, 0, 1],
[0, 0, 0, 1, 0, 0, 0, 1],
[0, 1, 0, 0, 1, 1, 0, 1],
[0, 1, 1, 1, 0, 0, 1, 1],
[0, 1, 0, 0, 0, 1, 0, 1],
[0, 0, 0, 1, 0, 0, 0, 1],
[0, 1, 1, 1, 0, 1, 0, 0],
];
function findMazePath (x, y) {
if (x < 0 || y < 0 || x >= N || y >= N) return false;
if (LOADS[x][y] != PATHWAY_COLOR) return false;
if (x === N -1 && y === N - 1) {
LOADS[x][y] = PATH_COLOR;
return true;
}
LOADS[x][y] = PATH_COLOR;
if (findMazePath(x - 1, y) ||
findMazePath(x, y - 1) ||
findMazePath(x + 1, y) ||
findMazePath(x, y + 1)) {
return true;
}
LOADS[x][y] = BLOCKED_COLOR;
return false;
}
findMazePath(0, 0);
console.log(LOADS);
JavaScript
복사
counting cells in a Blob
// 인접한 모든 이미지 그룹의 갯수를 구하라
var BACKGROUND_COLOR = 0;
var IMAGE_COLOR = 1;
var ALREADY_COUNT = 2;
function countCells (x, y) {
var result;
if (x < 0 || x >= N || y < 0 || y >= N) retunr 0;
if (grid[x][y] != IMAGE_COLOR) return 0;
grid[x][y] = ALREADY_COUNT;
return 1 + countCells(x - 1, y + 1) + countCells(x, y + 1) + countCells(x + 1, y + 1)
+ countCells(x - 1, y) + countCells(x + 1, y) + countCells(x - 1, y - 1)
+ countCells(x, y - 1) + countCells(x + 1, y - 1);
}
JavaScript
복사
N-Queens Problem
// 임의의 자연수 N 이 주어지면 N x N 의 이차원 체스보드가 생성되며, N개의 queen 이
// N 개 놓여질 수 있는지 (Queen 은 같은 행, 열, 대각선에 놓이면 안된다)
// back tracking 기법을 사용해서 해결한다
var cols = [];
function queens (level) {
if (!promising(level)) return false;
if (level === N) retunr true;
for (var i = 1; i <= N; i++) {
cols[level + 1] = i;
if (queens(level + 1)) return true;
}
return false;
}
function promising (level) {
for (var i = 1; i < level; i++) {
if (cols[i] === cols[level]) return false;
if (level - i == Math.abs(cols[level] - cols[i])) return false;
}
return true;
}
queens(0);
JavaScript
복사
멱집합 (powerset)
// 임의의 집합 data 의 모든 부분 집합을 출력하라
var LIST = ['a', 'b', 'c', 'd', 'e', 'f'];
function powerSet (originList) {
printStr(originList, false, '', 0);
printStr(originList, true, '', 0);
function printStr(originList, isInclude, str, level) {
if (isInclude) str += originList[level];
if (level === originList.length - 1) return console.log(str);
printStr(originList, false, str, level + 1);
printStr(originList, true, str, level + 1);
}
}
JavaScript
복사