재귀함수

재귀함수란?

💡 함수가 자기 자신을 호출하는 행위를 재귀호출이라고 합니다.
이렇게 재귀호출을 실행하는 함수를 재귀함수라고 합니다. 재귀함수에 대해서 알아보았습니다.

팩토리얼 구하기

1) 함수 선언문 방식

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

2) 함수 리터럴 방식

var fact = function f(n) {
	if (n <= 1) return 1;
    return n * f(n - 1); // 함수 f는 함수 내에서만 유효하다.
}

주의!

• 재귀함수는 반드시 멈춰주어야 합니다. (위의 예제의 경우 n이 1이상일 경우 멈춰준다.)
• 따라서 재귀함수는 재귀호출로 문제를 더 간단히 해결할 수 있을 때만 사용하도록 합니다. (호출 횟수만큼 메모리 소비량이 늘기 때문에 반복문을 쓰는게 메모리 공간을 더 적게 차지하기 때문입니다.)

재귀호출 예제

하노이의 탑

function hanoi(n, from, to, other) {
	if (n === 1) return;
    
    hanoi(n - 1, from, other, to);
    console.log("n번째 원판: " + from + "에서 " + to + "로 이동"); // 마지막 원반을 목적지로 이동
    hanoi(n - 1, other, to, from); // 나머지 원반들을 목적지로 이동
}

퀵정렬

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[0]; //기준점
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat(pivot, quickSort(right));
}

var arr = [7, 2, 5, 1, 8, 9, 3];
console.log(quickSort(arr));