[코드스테이츠 TIL] 재귀 Recursion

 

 

재귀 : 함수를 스스로 호출하는 것

 

- 기본적으로 반복문이므로 모든 재귀는 반복문으로 표현 가능하다

- 무한 반복을 방지하기 위해 반드시 탈출 조건이 있어야 한다

 

//재귀
function factorial(n) {
	//base case : n이 0이면 재귀를 더 이상 진행하지 않는다
	if(n===0){
		return 1;
	}
	//recursive case
	return n * factorial(n-1);
}

//반복
function factorial(n) {
	let result = 1;
	for (let i=n; i>0; i--) {
		result = result * i;
	}
	return result;
}

 

• 재귀의 사용 : 피보나치 수열, 돔 트리 구조 탐색
• 재귀의 장점 : 알고리즘이 재귀로 표현하기 자연스러울경우 프로그램 가독성이 좋다
• 재귀의 단점 : 값이 리턴되기 전까지 호출마다 call stack을 새로 생성하므로 반복문보다 메모리를 많이 사용한다