재귀함수 (Recursion Function) / JS

 

[재귀함수]

 

재귀 함수에 대하여 알아보자!

 

---

 

<STUDY>

 

재귀 함수 (Recursion Function)

자기 자신을 호출하는 함수

• 함수 내부에서 자기 자신을 호출함

 

💡 재귀 사용 이유

모든 곳에서 사용되기 때문!

 

 

❓재귀 함수가 자기 자신을 계속 호출한다면?

1. 함수 호출시 호출 스택 위에 함수가 쌓임
2. 반환 키워드를 확인하거나, 함수 안에 더이상 실행할 코드가 없는 경우 컴파일러가 호출 스택 가장 위에 있는 항목을 제거함

💡 호출 스택

함수가 올바른 순서대로 실행되도록 하는 자바스크립트의 정적 데이터 구조 (보이지 않는 곳에서 작동함!)

 

 

예시

function takeShower() {
	return "Showering!"
}

function eatBreakfast() {
	let meal = cookFood();
	return `Eating ${meal}`;
}

function cookFood() {
	let items = ["Oatmeal", "Eggs", "Protein Shake"];
	return items[Math.floor(Math.random()*items.length)];
}

function wakeUp() {
	takeShower();
	eatBreakfast();
	console.log("Ok ready to go to work!");
}

wakeUp();

 

# 호출 스택

[wakeUp] → [wakeUp, takeShower] → [wakeUp, eatBreakfast] → [wakeUp, eatBreakfast, cookFood] → [wakeUp, eatBreakfast] → [wakeUp] → []

 

 

재귀 함수 조건

• 다른 입력값
• 중단점 (종료 지점) 필요! (라인을 끝내는 종료 조건) ⇒ 종료 조건에서 반환문이 필요함

 

 

## 예시

• 입력된 값에서 1까지 연속적으로 출력하는 함수

function countDown(num) {
	if (num <= 0) {
		console.log("All done!");
		return;
	}
	console.log(num);
	num--;
	countDown(num);
}

countDown(5); // 5 4 3 2 1 All done!

 

# 호출 스택

[countDown(5)] → [countDown(4)] → [countDown(3)] → [countDown(2)] → [countDown(1)] → [countDown(0)]

 

• 팩토리얼

- 반복문

function factorial(num) {
	let total = 1;
	for (let i = num; i > 0; i--) {
		total *= i;
	}
	return total;
}

factorial(4); // 24

 

- 재귀 호출

function factorial(num) {
	if (num === 1) return 1;
	return num * factorial(num - 1);
}

factorial(4); // 24

 

 

# 호출 스택

[4 * facorial(3)] → [4 * factorial(3), 3 * facorial(2)] → [4 * factorial(3), 3 * facorial(2), 2 * factorial(1)] → [4 * factorial(3), 3 * facorial(2), 2 * factorial(1), return 1] → [4 * factorial(3), 3 * facorial(2), 2 * factorial(1)] → [4 * factorial(3), 3 * facorial(2)] → [4 * factorial(3)] → []

 

재귀 함수의 위험성

• 종료 조건이 없거나 잘못되는 경우 - 스택 오버플로 (stack overflow)⇒ 종료 조건에 반환문이 없는 경우 (return X)
• ⇒ factorial 예시에서 0이나 음수를 입력하는 경우

 

헬퍼 메소드 재귀 (헬퍼 함수)

외부 함수 안에서 정의되고 호출되는 재귀 함수

• 배열이나 데이터 목록 등을 컴파일할 때 사용하는 방법

 

## 예시 - 홀수 찾기

• 방법 1

function collectOdds(nums) {
	let result = [];
	
	function helper(helperInput) {
		if (helperInput.length === 0) return;
		if (helperInput[0] % 2 !== 0) result.push(helperInput[0]);
		
		helper(helperInput.slice(1));
	}
	helper(arr);

	return result;
}

collectOdds([1,2,3,4,5,6,7,8,9]); // [1,3,5,7,9]

 

• 방법 2

function collectOddValues(arr){
	let newArr = [];
	
	if (arr.length === 0) return newArr;
	if (arr[0] % 2 !== 0) newArr.push(arr[0]);

	newArr = newArr.concat(collectOddValues(arr.slice(1)));
	return newArr;
}

collectOddValues([1,2,3,4,5]);

 

 

---

 

알고리즘을 공부하면서 재귀 함수에 대한 이해가 부족하다는 생각이 많이 들어 정리해 보았다.

 

앞으로 조금 더 차근차근 공부해 나가야 할 것 같다.