재귀 함수(Recursion)

연쇄코딩마·2020년 10월 2일

복습

TIL

목록 보기

9/15

들어가기전에

자료구조에 대한 심도 있는 이해를 하기 위해 재귀함수나 복잡도를 잘 알아야 한다. 또한 재귀 함수를 잘하기 위해서는 잘게 쪼개어 사고하는 법을 배워야한다.

예를 들어 자연수를 합을 구한다고 생각하자

[1,2,3,4,5]

function arrSum(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

이 함수를 잘게 쪼갠다면 이렇게 만들수 있다.

arrSum([1, 2, 3, 4, 5]) = 5 + arrSum([1, 2, 3, 4]);
arrSum([1, 2, 3, 4]) = 4 + arrSum([1, 2, 3]);
arrSum([1, 2, 3]) = 3 + arrSum([1, 2]);
arrSum([1,2]) = 2 + arrSum([1]);
arrSum([]) = 0

이처럼 잘게 잘게 쪼개고 더 작은 경우로 나눠서 생각하고 해결하는 방법을 재귀함수라 한다.

그럼 언제 재귀함수를 사용하면 좋을까?

먼저 정리하자면

1. 주어진 문제가 더작은 문제로 나눠 질수 있는 경우

2. 중첩된 푸르가 많거나 중첩의 정도를 미리 알수가 없는 경우.

이 경우라도 재귀함수를 사용하지 않고도 루프를 통해 해결 할 수 있습니다. 그러나 재귀를 사용 할 경우 코드가 간결하며 이해하기 쉽다.

재귀적으로 사고하기

문제를 쪼개고 경우의 수를 나누기

예를 들어 아까 예를 가져오고자 한다.

arrSum([1, 2, 3, 4, 5]) = 5 + arrSum([1, 2, 3, 4]);

좌항은 우항과 같다는 건 고등학교만 나왔어도 이해할수 있겠다. 즉

arrSum([e1, e2, ... , en]) = e1 + arrSum([e2, ..., en])

으로 일반화 시킬수 있으며 e1 은 배열의 머리(head)가 된다. 나머지 함수에 감싸져 있는 부분은 꼬리(tail)가 된다.

function arrSum(arr) {
// 재귀의 기초 (base case)
// 문제를 더 이상 쪼갤 수 없을 경우
if (arr의 길이가 0인 경우) {
    return 0;
}
// recursive Case
// 그렇지 않은 경우
// head: 배열의 첫 요소
// tail: 배열의 첫 요소만 제거된 배열
return head + arrSum(tail);
}

로 풀이 할수 있다.

함수를 일반화 시킨 다면 다음과 같다.

function recursive(input1, input2, ...) {
  // 재귀의 기초 (base case)
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

재귀의 중요한 특성

function factorial(x) {
1  if (x<0) return;
2  if (x===0) return 1;
3  return x * factorial(x-1);
}

팩토리얼 흐름

factorial(3); 실행하면
1행에서 조건 패스
2행에서 조건 패스
return 3 * factorial(2);
factorial(2)에서 다시 함수 초입으로 올라간다.
1행에서 조건 패스
2행에서 조건 패스
return 2 * factorial(1);
factorial(1)에서 다시 함수 초입으로 올라간다.
1행에서 조건 패스
2행에서 조건 패스
return 1 * factorial(0);
factorial(0)에서 다시 함수 초입으로 올라간다.
1행에서 조건 패스
2행에서 조건에 부합하기 때문에 
factorial(0) = 1을 리턴한다. 이 조건에서 재귀는 멈춘다.

요약 하자면 return 3 * 2 * 1 
// 6

재귀의 특성은 크게 3가지로 나눌수 있다. 위 예시와 함께 설명하겠다.

종료 조건

if(더이상 조건을 쪼갤수 없는경우){return 정지}

종료조건은 재귀함수를 멈추는 조건이다.. 더 이상 조건을 쪼갤수 없을 때 재귀는 멈춰야된다. 위 예시if (x<0) return;에 해당한다. 팩토리얼은 음수는 곱하지 않는다. 문제에 따라 필요 없는 경우도 있다.

기반조건

if(만약에 쪼개다가 리턴하고 싶은 값을 만난다면?){return 성공값}

if (x===0) return 1;

이 조건은 종료 조건과는 비슷하나 성향은 다르다. 기반조건은 항상 존재 해야되며 팩토리얼은 숫자가 작아지며 곱해 나가야되며 x가 0을 만난다면 1을 곱해 재귀를 멈춰야 되기 때문에 꼭 있어야 한다.

재귀 조건

return x * factorial(x-1)

이 부분이다 본격적인 재귀가 일어나는 부분이다. 위에서 쪼개고 쪼개고 일반화 시킨 조건으로 코드를 작성해야되는 부분이다.

또 하나의 예제

function revStr(str) {
  if (str === '') return '';
  return revStr(str.substr(1)) + str[0];
}

revStr('cat')
revStr('cat')  returns revStr('at') + 'c'
revStr('at')   returns revStr('t') +  'a'
revStr('t')    returns revStr('') +   't'
revStr('')     returns               ''