알고리즘 - 재귀함수

재귀란?

자기 자신을 호출하는 함수를 말한다. 재귀함수에선 base case와 매번 다른 인풋이 주어지는 것이 매우 중요하다.

콜 스택

• 언제나 함수가 호출되면 스택의 맨위에 쌓인다.(push) 자바스크립트 코드는 실행되면서 return 키워드를 만나거나 함수가 끝나게 되면 컴파일러는 함수를 제거한다.(pop)
• 재귀함수를 작성하게 되면 계속해서 콜 스택에 새로운 함수가 쌓이게 된다. (언제 함수 호출을 멈추게 할지 포인트를 설정해주는 것이 중요하다!)

Base Case

언제 재귀함수가 멈추게 될지 정하는 조건이다.

재귀함수 예시

//재귀함수
function solution(num) {
	if(num <= 0) {
	console.log('done!');
}
console.log(num);
num--;
solution(num);
}

//for문
function solution(num)
	for(let i = num; i > 0; i--){
	console.log(i);
}
console.log('done!');
}

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

//재귀함수를 사용하여 팩토리얼 함수 작성하기
function factorial(num) {
  if (num === 1) return 1;
  return num * factorial(num - 1);
}

재귀함수를 작성할 때 항상 생각할 점

• base case를 두지 않는 것
• return을 하지 않거나 잘못된 값을 return 하게 되는 경우
• stack overflow!

Helper method

재귀함수를 작성할때의 패턴으로 재귀적이지 않는 outer 함수 내에 재귀함수를 작성하는 형식이다.

function outer(input) {
  let result = [];

  function helper(helperInput) {
    helper(helperInput--);
  }

  helper(input);

  return result;
}

Pure Recursion

function collectionOddValues(arr) {
  let newArr = [];

  //input 빈 배열인 경우 newArr를 리턴한다.
  if (arr.length === 0) return newArr;

  //첫번째 요소가 홀수면 newArr에 추가한다.
  if (arr[0] % 2 !== 0) newArr.push(arr[0]);

  //newArr는 기족 newArr의 새로운 재귀함수의 값을 합친 것이다.
  newArr = newArr.concat(collectionOddValues(arr.slice(1)));

  return newArr;
}

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

• newArr 정의시 concat이 아닌 push를 사용하게 되면 재귀함수는 새로 불러질때 계속 빈 배열로 재할당 되기 때문에 concat으로 연결해준다.
• helper method가 아닌 퓨어 재귀로 문제를 풀때 인풋으로 배열이 주어지면, **slice, 스프레드 연산자, concat**을 사용하여 배열을 수정하지 않고 카피하는 방법으로 활용할 수 있다.
• 문자열은 수정이 불가능하기 때문에 문자열을 카피하기 위해선 **slice, substr, substring**을 활용할 수 있다.
• 객체를 카피하기 위해선, Object.assign, 스프레드 연산자를 활용할 수 있다.