섹션7 재귀

스토리 타임: 마틴과 드래곤

기본 개념은 한 가지 문제를 가지고, 어떤 종료점에 도달할 때까지 더 작은 부분이나 변경되는 부분에서 반복적으로 수행하는 것이다. 그 종료점은 종료 조건 (base case)라고 한다.

재귀 함수를 사용하는 이유

재귀란 무엇인가?

: 자기자신을 호출하는 함수다.

왜 우리가 재귀를 알아야 하는가?

재귀는 모든 곳에 사용된다

• JSON.parse (보통 재귀적으로 작성됨) / JSON.stringify
• Ajax 호출을 하고 JSON이 반환된 후 그걸 자바스크립트로 만들때
• document.getElementById / DOM순회 알고리즘 (dom은 모든 요소가 중첩된 트리 구조로 되어 있다. )
• 객체 순회
• 우리가 데이터 구조나 트리, 그래프를 생성하고, 순회하고, 그 안에 있는 요소를 검색하고자 하는 경우
• 때로는 반복대신 재귀를 사용하는게 더 깔끔하다. (우리가 어려운 데이터 구조를 다루게 되고, 직접 parse 함수나 getElementById 함수를 작성할 때 정말 중요하다. 트리를 순회하는 것을 예로 들 수 있다.)

스택 호출하기

자바스크립트에서 함수를 호출할 때 보이지 않는 곳에서 무슨 일이 일어나는지 알아보자.
재귀 함수가 자기자신을 계속 호출하고 또 호출한다면, 보이지 않는 곳에서는 어떤 일이 벌어질까?
=> 거의 모든 프로그래밍 언어에는 보이지 않는 곳에서 함수 호출을 관리하는 일종의 데이터 구조가 있다.
=> 호출된 함수는 다른 함수가 반환될 때까지 기다리는 경우가 많다.
=> 함수가 올바른 순서대로 실행되어야 한다. 그걸 담당하는 데이터 구조가 있는데, js에서는 호출 스택이다.

콜스택 (The call stack)

• 실제로는 스택이라는 데이터 구조다.
• 함수를 호출하면, 호출 스택의 꼭대기에 쌓인다는게 전부다.
• 자바스크립트가 반환 키워드를 확인하거나, 함수안에 더이상 실행할 코드가 없으면 컴파일러가 스택의 제일 위에 있는 항목을 제거한다.
• 우리가 재귀함수를 사용할때, 우리는 새로운 함수를 계속 콜 스택에 넣는다.
• 호출스택은 자바스크립트의 보이지 않는 곳에서 작동하는 정적 데이터 구조이다.

첫번째 재귀 함수

어떤 재귀함수든 반드시 갖춰야 하는 두가지 요소가 있다.
1) Base case (종료 조건)
: 재귀가 멈추는 시점
2) 다른 입력값
: 매번 다른 데이터를 가진 함수를 호출하고 싶은 것이다.

function countDown(num){
	if(num <= 0){
    	console.log("All done!!!");
        return; //return을 해줘야 종료된다.
    }
  console.log(num);
  num--;
  countDown(num)
}

두번째 재귀 함수

function sumRange(num){
	if(num ===1) return 1 
    return num + sumRange(num-1)
}

숫자가 커지면 커질수록 스택에 훨씬 더 많은 함수 호출이 쌓이기 때문에 조심해야 한다.

반복문으로 팩토리얼 구현하기

재귀 함수 사용법을 가장 고전적으로 설명하는게 팩토리얼이다.

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

재귀 호출로 팩토리얼 구현하기

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

통상적인 재귀의 잠재적 위험

재귀 솔루션을 작성할 때 흔히 발생하는 문제들

• No base case (종료조건이 없는 것)
• Forgetting to return or returning the wrong thing! (값을 반환하는 것을 잊는것, 잘못된 값을 반환하는 것)
• Stack overflow (재귀가 멈추지 않는다는 뜻. 종료점이 없어서)

Helper 메소드 재귀

헬퍼 메소드 재귀는 일종의 결과를 컴파일할 때 흔히 사용되는 패턴이다.
결과는 보통 배열이나 배열과 비슷한 다른 형태 데이터 구조이다.
헬퍼 메소드 재귀는 그냥 재귀적이지 않은 외부 함수가 재귀적인 내부 함수를 호출하는 패턴이다.

우리가 배열이나 데이터 목록 같은 걸 컴파일해야 할 때 흔히 이렇게 작업한다.

function outer(input){
	var outerScopedVariable = []
    function helper(){
    	//modify the outerScopedVariable
      helper(helperInput--)
    }
  helper(input)
  return outerScopedVariable; 
}

배열 안에 있는 홀수 값들을 모두 모아보자!!!
=> 빈 배열을 생성하고 그 안에 모든 데이터를 입력한다.

function collectOddValues(arr){
	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; 
}

순수 재귀

• 헬퍼 메소드가 없고, 재귀만 사용한다. 그리고 위에 코드보다 더 짧다.
• collectOddValues는 짝수와 홀수 배열을 사용하며, 배열에서 추출된 홀수만 반환해야 한다.
• 순수 재귀의 경우 필요한 모든 코드가 함수 자체에 포함되며 재귀적이다.

function collectOddValues(arr){
	let answer = []; //이 배열은 함수가 재귀적으로 호출될 때마다 텅 비게 된다. 
  if(arr.length === 0){
  	return newArr; 
  }
  if(arr[0] % 2 !== 0){
  	newArr.push(arr[0]);
  }
  
  newArr = newArr.concat(collectOddValues(arr.slice(1)));
  return newArr; 
}

이런식으로 재귀 호출이 이뤄진다.

몇가지 tips

• 배열을 사용하고 헬퍼 메소드 없이 순수 재귀 솔루션을 작성하는 경우에, 배열을 복사하는 slice, spread 연산자(operator), concat같은 메소드를 사용할 수 있다. 그러면 배열을 변경할 필요가 없다. 일종의 결과를 축적할 수 있다.
• 문자열은 변경할 수 없다. 그래서 slice나 substring을 사용해서 사본을 만들어야 한다.
• 객체의 경우, Object.assign이나 spread 연산자를 사용하는게 유용하다.