재귀

자기 자신을 참조하는 것

재귀 함수는 반드시 탈출 조건(=기저 조건)을 갖고 있어야 한다.

function factorial(number) {
	if (number == 1 || number == 0) {
		return 1;
	} else {
		return number * factorial(number - 1);
	}
}

콜스택(=스택)

함수가 호출되면서 올라가는 메모리 영역

함수를 호출하면 해당 함수는 콜스택에 올라가게 되고, 함수가 종료되면 콜스택에서 제거된다.

콜스택의 메모리가 부족한 경우 재귀 함수는 자동으로 종료된다. 따라서 많은 재귀 함수를 호출하는 것보다 for문을 사용하는 것이 효율적이다.

재귀 활용

• 재귀를 사용해 단순히 반복 실행 하는 것은 성능 저하의 원인이 된다. 따라서 이런 경우에는 가급적 for문을 사용하자

• 재귀 함수는 상향식 계산보다는 하향식 계산에서 그 위력을 발휘한다. (상향식 계산은 for문으로도 구현할 수 있지만 하향식 계산은 오직 재귀 함수로만 구현할 수 있다.)

  // ⭕ 하향식 계산
  function factorial(number) {
  	if (number == 1 || number == 0) {
  		return 1;
  	} else {
  		return number * factorial(number - 1);
  	}
  }
  
  // ❌ 상향식 계산
  function factorial(number, i = 1; sum = 1) {
  	if(i > number) {
  		return sum;
  	}
  	return factorial(number, i + 1, sum * 1);
  }
  

• 하위 문제와 마지막 으로 나누어서 구현해보면 쉽다. ex) 2^5 = 2^4 X 2 로 바꾸어서 생각한 뒤 구현하면 쉽다.

  // 배열의 합 구현하기
  function sumArr(arr) {
  	if(arr.length == 1) {
  		return arr[0]; // 하나 남은 배열의 전체 합은 하나의 배열이기 때문에 그 자체를 리턴
  	}
  	sumArr(arr.slice(0, -1)) + arr[ar.length - 1]; // `0번 인덱스 ~ 마지막 - 1` + `마지막`
  }
  
  // 문자열의 길이 구현하기
  function strLength(str) {
  	if(str[0] == null) return 0;
  	return strLength(str.slice(0, -1)) + 1; // `0번 인덱스 ~ 마지막 - 1` + `마지막 길이`
  }
  
  // 지수함수 구현하기
  function power(x, n) {
  	if(n == 0) return 1;
  	return power(x, n - 1) * x;
  }
  

🤔 재귀 - 하노이 탑

function hanoi(count, from, to, temp) { // 총 개수, 시작, 도착, 거쳐가는 부분
	if(count == 0) return;	
	hanoit(count - 1, from, temp, to);
	console.log(`원반 ${count}를 ${from}에서 ${to}로 이동`);
	hanoi(count - 1, temp, to, from);
}