재귀 (Recursion)

재귀란

• 재귀는 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻함.

function addOne (num) {
	console.log(num);
	addOne(num + 1); // 자기 자신을 참조
}

• 재귀 함수는 기저조건이 꼭 필요함 (아니면 무한 실행됨)
  • 자기 자신을 참조하면서 함수가 끝나지 않기 때문에 스택에 계속 쌓이게 됨 => 메모리 부족으로 강제 종료됨.
  • 재귀함수가 for문보다 메모리 공간을 더 많이 차지함 => 더 복잡한 문제를 쉽게 해결하기 위함

function addOne (num) {
	if(num > 10) return;
	console.log(num);
	addOne(num + 1); // 자기 자신을 참조
}

재귀 유형

1. 반복실행 : 반복문보다 효율적이지 않음
2. 하향식 계산방법 : 하위문제의 결과를 기반으로 현재 문제를 계산하는 것 - 재귀함수 쓸 때 좋음

// arr : [0,1,2,3,4]

function getArrSum (arr) {
 if(arr.length === 1) return arr[0]
 return getSum(arr.slice(0,-1)) + arr[arr.length -1];
 // getSum(arr.slice(0,-1)) : 하위 문제 
 // arr[arr.length -1] : 시작점
}