Recursion 재귀

👉[JavaScipt 알고리즘 & 자료구조 마스터클래스 수업] 을 제공 받아 알고리즘 공부를 하고 있는데요!
유데미의 강점인 짱짱한 프로모션 기간이 있으니! 꼭 착한 가격에 알찬 강의 쟁겨가시길 바라요

재귀 함수란?

a propcess (a function in out cas) that calls itself

자기 자신을 호출하는 함수

자바스크립트에서 재귀 함수를 호출할 때 어떤 일이 일어날까?

자바스크립트와 같은 프로그래밍 언어에는 함수 호출을 정리하고 담당하는 데이터 구조(data structure)가 있다. 이것을 call stack 이라고 한다.

호출 스택은 자바스크립의 보이지 않은 곳에서 작동하는 정적 데이터 구조(static data structure)이다.

stack 맨 위의 함수를 실행하고, 리턴을 확인한 뒤, 컴파일러가 스택의 제일 위에 있는 함수를 제거한다.

재귀 함수는 어떻게 동작할까?

기본적인 개념은 동일한 함수를 반복적으로 호출하는 것이다. 하지만 영원히 반복한다면 과부하가 일어나고 하드웨어에 큰 악영향을 끼칠 것이다. 그래서 재귀함수는 base case즉, 종료 조건이 있어야 한다.

1. Base case (=stopping point) 종료 조건은 재귀를 멈추기 위해 만족해야 하는 조건이다.
2. Different Input
   여러가지 다른 데이터를 가지고 함수를 실행할 수 있어야 한다.

예시로 보기

//재귀를 사용한 경우
function sayHello(num){
	if(num <= 0){ //end point
		console.log('Hello');
		return; // return하는 것이 없더라도 꼭 return을 해줘야 함
	}
	console.log(num)
	num--;
	sayHello(num);
}

//반복문을 사용한 경우
function sayHello(num){
	for(let i = num; i > 0; i--){
		console.log(i);
	}
	console.log('Hello')
}

sayHello(3)

위의 예시에서 재귀 함수의 경우,
sayHello(0) 가 되면 num <= 0 이 되어 console.log('Hello') 가 작동한다. 이것이 바로 종료 조건이다.

return 해주는 것이 없더라 하더라도 재귀 함수를 사용할 때, 종료 조건 안에는 꼭! return을 포함해주어야 한다. 만약 리턴문이 없다면 컴파일러가 함수를 제거하지 않고 계속 진행될 것이다.

예시로 보기2 (base case)

function mul(num){
	if (num === 1) return 1; // num === 1 은 base case
	return num * mul(num-1);
}

위의 코드를 살펴보자

mul(5)를 실행한다면

mul(5) = 5*mul(4)
mul(4) = 4*mul(3)
mul(3) = 3*mul(2)
mul(2) = 2*mul(1)
mul(1) = 1

따라서 위의 함수는 num만큼의 숫자를 모두 곱한 값을 리턴한다.

예시로 보기 (팩토리얼)

//반복 함수로 구현
function factorial(n){
	const result = 1;
	for( let i = n; i > 1; i-- ){
		result *= i
	}
return result;
}

위의 팩토리얼을 반복문으로 구현한 함수를 재귀로 구현해보도록 하자.

//재귀로 구현 - **무한반복 에러**
function factorial(n){
	return n * factorial(n-1)
}

위의 코드는 엔드포인트, 종료지점이 없다. 무한 반복이 될 수 밖에 없다.
스택에 무한으로 함수가 쌓이는 것이다. 그러면 최대 호출 스택을 초과했다는 에러가 날 수 있고 이를 stack overflow 라고 한다.

//재귀로 구현
function factorial(n){
	if(n===1) return 1;
	return n * factorial(n-1)
}

이렇게 엔드 포인트를 걸어주면 무한 반복하지 않는 코드를 구현할 수 있다.

지금까지 구현한 재귀 함수는 단일 단독 함수(single standalone function) 이다. 외부에서 팩토리얼 함수를 호출하면 팩토리얼 함수는 직접 자체 코드 내의 팩토리얼 함수를 호출한다. 하지만 helper method 재귀는 단독 함수와 조금 다르다.

Helper method resursion 헬퍼 메소드 재귀

헬퍼 메소드 재귀의 기본 형태는 다음과 같다.
외부 함수 내에 재귀 함수가 들어있다.

//외부함수
function outer(input){
	let outerScopeVariable = []
	//재귀함수
	function helperRecursion(helperInput){
		helperRecursion(helperInput--)
	}
	helper(input)
	return outerScopedVariable;
}

배열이나 데이터 목록 같은 것을 컴파일 해야 할 때 헬터 메소드 재귀를 사용한다. recursive helper를 사용하면 빈 배열에 수집해야 하는 데이터들을 저장하기에 용이하다.

만약 재귀 함수 자체에서 배열 변수를 선언하게 된다면 함수를 호출할 때마다 배열 값이 리셋 될 것이다.

function collectNums(arr){
	let result = []; //호출 할 때 마다 재정의됨
	if(arr.length === 0){
			return;
		}
	...
}

위의 코드를 헬퍼 재귀로 수정해보자.

function collectNums(arr){
	let result=[]

	//헬퍼재귀
	function helperEvens(helperInput){
		//end point 종료 조건
		if(helperInput.length === 0){
			return;
		}
		if(helperInput[0] % 2 == 0){
			result.push(helperInput[0])
		}
		
		helperEvens(helperInput.slice(1))
	}
	
	helperEvens(arr)
	return result;
}

collectNums([1,2,3,4,5])

1. collectNums([1,2,3,4,5]) 은 collectNums 를 호출한다.
2. collectNums 안에 있는 helperEvens([1,2,3,4,5]) 가 호출된다.
3. [1,2,3,4,5] 의 길이가 0이 아니기 때문에 종료 조건은 패스한다. if(helperInput[0] % 2 == 0) 를 보면, helperInput[0] 인 arr의 인덱스 0인 1은 2로 나눠지지 않기 때문에 또 패스한다.
4. helperInput.slice(1) = [2,3,4,5] 이므로 helperEvens(helperInput.slice(1)) 에 의해 helperEvens([2,3,4,5]) 를 실행한다.
5. 두 번째 if문 에서 helperInput 배열의 인덱스 0인 2는 result 에 push된다. 그리고 또 slice로 인덱스 0을 잘라내고 그 뒤의 원소들을 재귀를 통해 짝수판별을 한다.
6. 마지막으로 helperInput 의 길이가 0이 되면 배열 result 에는 짝수만 남게 되고 return 된다.

💡 헬퍼 메소드 재귀는 외부 함수가 재귀적인 내부 함수를 호출하는 방식이다. 함수를 거친 값들을 새로운 배열에 저장하고 리턴하고 싶을 때 용이하다.

Pure recursion 순수 재귀

순수 재귀 함수란 함수에 모든 코드를 포함하고 재귀적으로 작동하도록 하는 것이다. 헬퍼 재귀와 달리 외부 함수, 내부 함수를 구분 지어 중첩 함수로 작성하는 것이 아니라 하나의 함수로 작성하는 것이다.

function collectEven(arr){
	let result = [];
	
	if(arr.length === 0){
		return result;
	}
	
	if(arr[0] % 2 === 0){
		result.push(arr[0]);
	}
	
	result = result.concat(collectEven(arr.slice(1)));
	return result;
}

collectEven([1,2,3,4,5])

1. collectEven([1,2,3,4,5]) 를 하면, 첫 조건문에서 길이가 0이 아니기 때문에 이 조건문은 패스한다. 두 번째 조건문에서도 arr[0]이 2로 나누었을 때 나머지가 0이 아니기 때문에 패스한다.
2. arr1.concat(arr2) 은 arr1과 arr2를 합하여 새로운 배열을 반환한다.
   result = result.concat(collectEven(arr.slice(1))); 에서 arr.slice(1) 는 [2,3,4,5] 이다.
   그 다음, collectEven(arr.slice(1)) 으로 함수를 재귀적으로 호출했기에 진행한다.
3. collectEven([2,3,4,5]) 에서 result에 2가 들어간다.
   [2].concat(collectEven([3,4,5]));이 되고 이를 자세히 나타내보자면
   

    collectEven([1,2,3,4,5])
    	[].concat(collectEven([2,3,4,5])) 
    		[2].concat(collectEven([3,4,5])) 
    			[].concat(collectEven([4,5])) 
    				[4].concat(collectEven([5])) 
    					[].concat(collectEven([]))
    						[]

거슬러 올라가 보면서 호출되는 값들을 확인하자면

   []
   	[].concat(collectEven([])) //collectEven([]) = [] => [].concat([])
   		[4].concat(collectEven([5])) //[4].concat([])
   			[].concat(collectEven([4,5])) //[].concat([4])
   				[2].concat(collectEven([3,4,5])) //[2].concat{[4])
   					[].concat(collectEven([2,3,4,5])) //[].concat([2,4])
   						collectEven([1,2,3,4,5])

리턴값은 `[2,4]` 로 짝수만 푸쉬된 배열이 만들어진다.

순수 재귀 Tips

1. slice the spread operator concat 같은 메소드를 활용하면 새로운 배열을 만들어 반환하기 때문에 배열 자체를 변경할 필요가 없다.
2. 문자열을 다룰 때 문자열은 immutable 하다. 변경, 수정이 불가하기 때문에 slice substr 등을 통해 복사본으로 활용하는 것이 좋다.
3. 객체를 다룰 때는 Object.assign 이나 the spread operator 연산자를 사용하여 딥한 복사를 하는 것이 원본을 방해하지 않기에 좋다.

문제를 풀어보자 🚀퀴즈 타임

이 강의의 장점은 이렇게 과제를 제공한다는 점이에요!

섹션 8은 재귀문제 집합이고 더 연습해보고 싶은 사람들을 위해 섹션 9 보너스 도전 재귀 문제 까지 있답니다!

아쉽게도 문제 집합 섹션은 재귀까지만 있어요.
아무래도 기초를 다잡고자 하는 것에 목적이 있는 강의이다 보니 과제가 모든 개념들에 제공되진 않습니다!

그래서 유데미 [JavaScript 알고리즘 & 자료구조 마스터클래스] 로 개념을 다잡고 백준으로 해당 개념에한 추가적인 문제를 풀어보는 것이 가장 베스트라고 생각합니다!