재귀를 알아보자

목차

1. 재귀란 무엇이며 어떻게 사용되는가?
2. 재귀형 함수를 작성할 때 반드시 필요한 두 가지
3. 헬퍼 메소드를 사용하는 재귀 VS 순수 재귀

---

재귀 함수란

재귀는 자기자신을 호출하는 과정이다. 즉, 재귀라고 하면 자기자신을 호출하는 함수를 말한다.

그렇다면 재귀 함수는 영원히 자기자신을 호출할까?
그렇지 않다면 언제 멈출까?
콜 스택이 계속해서 쌓이게 될텐데, 이는 어떤 방식으로 작동하는 것일까?

재귀 함수가 동일한 함수를 계속해서 호출한다는 것이 기본 개념은 맞지만, 반드시 멈추는 지점이 있어야 한다.
우리는 그것을 기반조건(base case)이라 부르기로 했다.

기반 조건(base case)

기반조건이란 재귀가 멈추는 지점이다. 재귀란 반드시 끝나는 지점이 있어야 한다. 그냥 자신을 영원히 호출하는 게 아니다. 이를 위해서 재귀 함수는 조건을 가져야 하는데, 그것이 기반 조건이다.

재귀형 함수를 작성할 때 반드시 필요한 두 가지

첫째로는, 기반 조건이 필요하다는 것이며
둘째로는, 재귀가 반복될 때마다 매번 다른 인풋값이어야 한다는 것이다.

따라서 우리가 재귀를 사용하고자 할 때 기반 조건은 무엇이 되어야 하며, 매번 어떤 인풋값을 넣어주어야 할 지에 대한 탄탄한 로직이 뒷받침되어야 한다.

다음 예를 함께 보자.

function countdown(num) {
  if (num <= 0) {
    console.log("All Done");
    return;
  }
  console.log(num);
  num--;
  countdown(num);
}

위 함수는 입력한 숫자에서 시작해서 숫자를 1씩 빼가면 쭉 출력한다. 예를 들어 5를 입력하면 5, 4, 3, 2, 1이 출력된다.

위의 예시의 기반조건은 무엇인지, 인풋값은 매번 다르게 들어가고 있는지 체크해보자.

1. 기반 조건은 다음과 같다. if (num <= 0)
2. num의 값을 1씩 마이너스 해줌으로써, 매번 다른 인풋값이 들어가고 있다.

다음 예시도 한번 봐보자.

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

다시 한번 위의 예시도 기반조건이 존재하는지와 매번 다른 인풋값이 들어가는 지 체크해보자.

1. 기반 조건은 다음과 같다. if (num === 1)
2. num의 값을 1씩 마이너스 해줌으로써, 매번 다른 인풋값이 들어가고 있다.

만약 기반 조건을 작성하지 않고 계속해서 자기 자신을 호출하게 된다면 어떻게 될까?
콜 스택이 차서 흘러넘치는, 흔히 스택오버플로우 현상이 나타나게 될 것이다.

다음은 재귀 함수의 예시로 흔히 등장하는 팩토리얼 예시이다.

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

// 2. using recursive
// 기반 조건과 매번 달라져야 하는 인풋을 이해해보자. 
fucntion factorial(num) {
 if(num === 1) return 1;
 return num * factorial(num - 1)
}

만약 우리가 만든 재귀함수가 제대로 작동하지 않는다면 다음과 같은 항목들을 재검토하도록 하자.

1. 기반조건이 존재하는가? 존재한다 하더라도 올바른 기반조건이 맞는가?
2. 리턴값을 잊지는 않았는가? 혹은 잘못된 것을 리턴하고 있지는 않은가?
3. 스택오버플로우 현상이 일어나고 있는 것이 아닌가?

---

헬퍼 메소드를 사용하는 재귀 VS 순수 재귀

재귀와 함께 흔히 사용되는 헬퍼 메소드

헬퍼 메소드 재귀는 재귀형이 아닌 외부 함수가 재귀형인 내부 함수를 호출하는 형태이다.

헬퍼 메소드는 재귀와 함께 사용되는 설계 패턴이다. 이제까지 위에서 작성했던 모든 재귀 함수는 팩토리얼처럼 단일 단독 함수였다. 즉 스스로 재귀를 한다.

헬퍼 메소드 재귀는 조금 다르다.
헬퍼 메소드 재귀에는 두 개의 함수가 있다.
다음 코드를 보자.

function outer(input) { // 외부 함수 outer function, 외부 함수는 개발자인 우리가 외부에서 호출하게 된다. 
  // 우리는 외부 함수를 호출해서 내부 함수로 인자를 전달할 수 있다. 내부함수는 재귀적으로 자기자신을 호출한다.
 let outerScopedVariable = [];
  
 function helper(helperInput) { // 내부의 재귀 함수 helper function
  // outerScopedVariable를 수정시킨다.
   helper(helperInput--);
 };
  
 helper(input);
  
 return outerScopedVariable;
}

위의 코드는 헬퍼 메소드 재귀의 한 예시이다.
위와 같은 설계는 배열이나 데이터 목록을 컴파일 하게 될 때 흔히 작업하는 패턴이다.

다음 예시를 보자.
어떠한 숫자들을 포함하고 있는 한 배열에서 모든 홀수값을 수집하는 작업을 헬퍼 메소드 재귀를 사용하여 수행하려고 한다.

function collectOdd(arr) {
  // 빈 배열을 생성한다. 
  let result = [];
  
  function helper(helerInput) {
    if (helperInput.length === 0) {  // 기반 조건(종료 조건)이다. helperInput의 길이가 0이라면 모든 number에 대한 루프를 다 돈거나 마찬가지이니 재귀를 종료한다.
      return; 
    }
    
    if (helperInput[0] % 2 !== 0) {  // 홀수라면 helperInput[0]을 result 배열에 추가한다.
      result.push(helperInput[0]); 
    }
    
    helper(helperInput.slice(1));  // 재귀적으로 자기자신을 호출한다. 새로 들어가는 인풋값은 기존의 helperInput의 첫번째 값을 빼준 더 작은 새로운 배열이다. 
  }
  
  helper(arr);
  
  return result;
};

순수 재귀

위에서는 헬퍼 메소드 재귀를 통해서 collectOdd 함수를 구현했다.
헬퍼 메소드 재귀가 한 가지의 방법이긴 했지만 유일한 방법은 아니며 순수 재귀를 이용해서도 같은 작업을 수행할 수 있다.

따라서 이번에는 collectOdd 함수를 순수 재귀로 구현해보도록 하자.
순수 재귀의 경우 모든 코드가 함수 자체에 포함되며 재귀적이다.
코드를 봐보도록 하자.

function collectOdd(arr) {
  // 함수가 호출될 때마다 newArr 변수를 정의한다.
  // 이 배열은 함수가 재귀적으로 호출될 때마다 텅 비게 될 것이다.
  // 헬퍼 메소드 재귀와의 차이점은 배열이 리셋되도 상관이 없다는 것이다.
  let newArr = [];
  
  // 배열에 입력된 값이 없는지 확인한다. 입력된 값이 없다면 newArr를 반환한다.
  if (arr.length === 0) {
   return newArr; 
  }
  
  // 배열의 첫 번째 숫자가 홀수인지 확인한다. 홀수라면 newArr에 push한다.
  if (arr[0] % 2 !== 0) {
   newArr.push(arr[0]); 
  }
  
  // 모든 계산이 완료되었다면, 모든 배열을 한 배열로 합쳐서 반환하는 것이다.
  newArr = newArr.concat(collectOdd(arr.slice(1)));
  return newArr;
};

collectOdd([1, 2, 3, 4, 5]); // [1, 3, 5]
  // 이해를 위해서 작동 방식을 하나하나 들여다보자.
  // arr[0] 은 1이다. 따라서 newArr에 들어가있다. 그렇다면 현재 newArr은 [1] 의 상태를 가진다. 따라서 밑의 코드는 다음과 같이 동작한다.
  // [1].concat(collectOdd([2, 3, 4, 5]));
  // 위의 collectOdd([2, 3, 4, 5]) 이 동작하게 되면 [2, 3, 4, 5]를 가지고 새롭게 함수가 동작한다.
  // newArr은 다시 리셋될 것이고, arr.length는 0이 아니니 건너뛴다. 또한 arr[0] 은 2이므로, 홀수가 아니고 따라서 newArr에도 추가하지 않는다.
  // 그렇다면 현재의 newArr 의 상태값은 다음과 같다. [], 빈 배열이다.
  // 다시 재귀적으로 함수를 호출하자 
  // newArr = [].concat([3, 4, 5]); 와 같을 것이다.
  // ... (생략)
  // 이와 같은 방식을 표현식으로 나타내면 아래의 그림과 같다.

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

이런 식으로 순수 재귀를 사용해서 같은 문제를 해결할 수 있다.
개인적으로는 헬퍼 메소드 재귀가 훨씬 더 직관적인 것 같다.
즉 언제나 순수 재귀를 사용해서 작업을 할 수 있긴 하다만 헬퍼 재귀 함수가 좀 더 직관적이라 코드의 로직을 생각하기 쉽다.

자 이제 마지막으로 재귀 함수를 구현할 때 주의해야 하는 점을 알아보자.
첫째로 배열의 경우, 기존의 배열을 변경하지 않도록 배열 복사본을 만드는 slice, spread operator 및 concat과 같은 방법을 사용하는 것을 권장한다.
둘째로 문자열 같은 경우, 문자열은 변경할 수 없으므로 문자열의 복사본을 만들려면 slice, substr 또는 substring과 같은 메서드를 사용해야 한다.
마지막으로 객체의 경우, 객체의 복사본을 만들려면 Object.assign 또는 스프레드 연산자를 사용해야 한다.

---