8. 알고리즘 - 재귀

재귀

• 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 말한다.
• 재귀 함수는 기저조건(종료되는 조건)이 반드시 있어야 한다.
• 기저조건이 없는 재귀함수를 실행하면 메모리 부족으로 함수가 강제 종료 된다.
• 재귀함수 내에서 자기자신을 호출할 때 이미 이 함수 구현되어 있다고 가정한다.
• 하향식 계산에 사용된다.

콜스택

• 함수가 호출되면서 올라가는 메모리 영역
• 먼저 들어온 데이터가 나중에 나간다.
• 스택 자료구조를 잘 활용한 대표적인 사례

팩토리얼 - n이 주어졌을때 1부터 n까지 모든 수의 곱을 말한다.

5! 와 같이 작성 한다.

배열의 합 (재귀적으로 구하기 하향식 방법)

[1, 2, 3, 4, 5]의 배열의 합을 구할 때 하위문제의 결과는 [1, 2, 3, 4]의 배열의 합이고 이 배열의 합에 5를 더하면 된다.

function suArray(arr){
  return sumArray(arr.slice(0, -1)) 배열의 0부터 배열의끝에서 한칸 전까지 자른 배열의합 
}

function suArray(arr){
  return sumArray(arr.slice(0, -1)) + arr[arr.length -1 ]; 배열의 마지막 원소 더하기
}

function suArray(arr){
  if(arr.length == 1) return arr[0]; 배열이 하나 남으면 자기 자신의 값을 반환하기(기저 조건)
  return sumArray(arr.slice(0, -1)) + arr[arr.length -1 ];
}

function suArray(arr){
  if(arr.length == 1) return arr[0];
  return sumArray(arr.slice(0, -1)) + arr[arr.length -1 ];
}
let arr = [1,2,3,4,5];
let sum = sumArry(arr);
console.log(sum);
// 15 가 출력

글자의 길이 (재귀적으로 구하기 하향식 방법)

function strLength(arr){
  return strLength(arr.slice(0, -1));배열의 0부터 배열의끝에서 한칸 전까지 자른 배열의합
}

function strLength(arr){
  return strLength(arr.slice(0, -1)) + 1;하나 남은 글자의 숫자는 1이므로 1을 더해준다.
}

function strLength(arr){
  if(arr[0]== null) return=0; 배열이 비었을 경우 글자의 길이는 0이기 때문에 0을 반환 (기저 조건)
  return strLength(arr.slice(0, -1)) + 1;
}

function strLength(arr){
  if(arr[0]== null) return=0; 배열이 비었을 경우 글자의 길이는 0이기 때문에 0을 반환 (기저 조건)
  return strLength(arr.slice(0, -1)) + 1;
}
let str = "abcde"
let len = strLength(str);
console.log(len);
// 5가 출력 된다.

지수 함수 (재귀적으로 구하기 하향식 방법)

function power(x, n){
  return power(x, n-1); x의 n-1의 제곱을 구하는 식
}

function power(x, n){
  return power(x, n-1) * x; x의 n의 제곱을 구하기 위해 x를 곱해준다.
}

function power(x, n){
  if(n==0) return x=1;
  return power(x, n-1) * x; x의 n의 제곱을 구하기 위해 x를 곱해준다.
}

function power(x, n){
  if(n==0) return 1;
  return power(x, n-1) * x; x의 n의 제곱을 구하기 위해 x를 곱해준다.
}
console.log(power(2, 5));
// 32가 출력

재귀 - 하노이탑

function hanoi(count, from, to, temp) {
	if (count == 0) return;
	hanoi(count - 1, from, temp, to); // 원반 1,2가 A에서 시작 B로이동 하는데 C를 임시로 사용
	console.log(`원반 ${count}를 ${from}에서 ${to}로 이동`);
	hanoi(count - 1, temp, to, from); // B에 있는 원반1,2를 C로 이동 하는데 A를 임시로 사용
}

hanoi(3, 'A', 'C', 'B'); // 원반의 갯수 A에서 C로 이동하고 B를 임시로 사용

위 함수를 실행하면 아래와 같은 순서로 실행 된다.

function hanoi(3, A, C, B) {
	if (3 == 0) return;//1
	hanoi(3 - 1, A, B, C);//2 
	console.log(`원반 ${3}를 ${A}에서 ${C}로 이동`);//15
	hanoi(3 - 1, B, C, A); //16
}

function hanoi(2, A, B, C) { //2
	if (2 == 0) return;//3
	hanoi(2 - 1, A, C, B);//4 
	console.log(`원반 ${2}를 ${A}에서 ${B}로 이동`);//9
	hanoi(2 - 1, C, B, A); //10
}

function hanoi(1, A, C, B) { //4
	if (1 == 0) return;//5
	hanoi(1 - 1, A, B, C);//6 
	console.log(`원반 ${1}를 ${A}에서 ${C}로 이동`);//8
	hanoi(1 - 1, B, C, A); //9
}

function hanoi(0, A, B, C) { //6
	if (0 == 0) return;//7 
	hanoi(0 - 1, A, C, B); 
	console.log(`원반 ${0}를 ${A}에서 ${B}로 이동`);
	hanoi(0 - 1, C, B, A); 
}

function hanoi(1, C, B, A) {//10
	if (1 == 0) return;//11
	hanoi(1 - 1, A, C, B); //12
	console.log(`원반 ${1}를 ${C}에서 ${B}로 이동`);//13
	hanoi(1 - 1, A, B, C); //14
}

function hanoi(2, B, C, A) {//16
	if (2 == 0) return;//17
	hanoi(2 - 1, B, A, C);//18
	console.log(`원반 ${2}를 ${B}에서 ${C}로 이동`);//23
	hanoi(2 - 1, A, C, B); //24
}

function hanoi(1, B, A, C) {//18
	if (1 == 0) return;//19
	hanoi(1 - 1, B, C, A);//20
	console.log(`원반 ${1}를 ${B}에서 ${A}로 이동`);//21
	hanoi(1 - 1, C, A, B); //22
}

function hanoi(1, A, C, B){//24
    if(1 == 0) return;//25
    hanoi(1 - 1, A, B, C);//26
    console.log(`원반 ${1}를 ${A}에서 ${C}로 이동`)//27
    hanoi(1 - 1, B, C, A )//28
}

실행하면 아래와 같이 출력

λ node hanoi.mjs 
원반 1를 A에서 C로 이동
원반 2를 A에서 B로 이동
원반 1를 C에서 B로 이동
원반 3를 A에서 C로 이동
원반 1를 B에서 A로 이동
원반 2를 B에서 C로 이동
원반 1를 A에서 C로 이동