[JavaScript] 재귀 😵‍💫

재귀 호출(recursive call)

함수가 자기 자신을 호출하는 행위

 

재귀 함수

재귀 호출을 수행하는 함수

 

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제;
}

 

☄️ 재귀 함수 유의 사항

1. 재귀 호출은 반드시 멈춰야 한다

 

2. 재귀 호출로 문제를 간단하게 해결할 수 있을 때만 사용한다

호출된 각각의 재귀 함수는 다른 메모리 영역을 사용한다. 따라서 호출된 횟수만큼 메모리 소비량이 늘어난다. 반복문을 재귀 함수로 표현할 수 있지만 대부분은 while 문이나 for 문으로 작성하는 편이 이해하기 쉽고 메모리 공간도 적게 차지한다.

 

🔖 재귀 함수 예시

n의 팩토리얼을 구하는 함수

function fact(n) {
	if(n <= 1) return 1;
    return n*fact(n-1);
}

fact(5);	// -> 120

 

하노이의 탑

function hanoi(n, a, b, c) {
	if(n < 1) return;
    hanoi(n-1, a, c, b);
    console.log(n + " 번째 원반: " + a + " -> " + c);
    hanoi(n-1, b, a, c);
}

hanoi(4, "A", "B", "C");

 

퀵 정렬

(1) 적당한 값 p를 고른다. p를 고를 때는 가능한 그 값의 크기가 p 값 이상인 요소의 개수와 p 값 이하인 요소의 개수가 같도록 한다

(2) 배열 앞부분에는 p 값 이상인 요소를 옮기고, 배열 뒷부분에는 p 값 이하인 요소를 옮긴다

(3) 배열 앞부분의 길이가 2 이상이면 그 부분을 대상으로 퀵 정렬

(4) 배열 뒷부분의 길이가 2 이상이면 그 부분을 대상으로 퀵 정렬

/*
 * x : 정렬할 배열
 * first : 정렬할 첫 번째 요소의 위치
 * last : 정렬할 마지막 요소의 위치
 */
 
function quicksort(x, first, last) {
	let p = x[Math.floor((first+last)/2)];
    for(let i = first; j = last; j--) {
    	while(x[i] < p) i++;	// 왼쪽부터 차례대로 p 이상의 요소를 검색
        while(p < x[j]) j--;	// 오른쪽부터 차례대로 p 이하의 요소를 검색
        if(i >= j) break;		// i와 j가 교차하면 다음으로 이동
        // 발견하면 x[i]와 x[j]를 교환
        let w = x[i];
        x[i] = x[j];
        x[j] = w;
    }
    if(first < i-1) quicksort(x, fist, i-1);	// 왼쪽에 두 개 이상 남아 있으면 왼쪽을 다시 정렬
    if(j+1 < last) quicksort(x, j+1, last);		// 오른쪽에 두 개 이상 남아 있으면 오른쪽을 다시 정렬
}

let a = [7, 2, 5, 1, 8, 9, 3];
quicksort(a, 0, a.length-1);
console.log(a);		// -> [1, 2, 3, 5, 7, 8, 9]

 

모던 자바스크립트 입문