재귀(recursion)

yezo cha·2021년 6월 15일

Data Structure & Algorithm

목록 보기

1/15

Recusion 재귀

문제 해결을 하다 보면 함수에서 다른 함수를 호출해야 할 때가 있다. 이때 함수가 자기 자신을 호출할 수도 있는데, 이를 재귀 라고 부른다.

함수가 자신을 호출하는 단계를 재귀 단계(recursion step)라고 부른다. basis라고도 불리는 재귀의 베이스(base)는 작업을 아주 간단하게 만들어서 함수가 더 이상은 서브 호출을 만들지 않게 해주는 인수이다.

다르게 생각하기 - 문제를 쪼개어 생각하는 방법

자연수로 이루어진 배열의 합을 두 가지 방식으로 구현해보자.

반복적인 사고를 통한 방법 : for loops

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

재귀적인 사고를 통한 방법 : 작업을 단순화하고 자기 자신을 호출함.
어떤 문제를 해결할 때, 동일한 구조의 더 작은 문제를 해결함으로써 주어진 문제를 해결하는 방법을 재귀(recursion)라고 한다.

function sumTo(num) {
  // sumTo(n)은 자연수 1부터 n까지의 합을 계산하는 함수.
  // sumTo(1) = 1
  // sumTo(2) = 1 + 2 = 3
  // sumTo(3) = 1 + 2 + 3 = 6
  if(num <= 1) {
    return num;
  }
  return num + sumTo(num-1);
}

재귀를 사용한 코드는 짧다.
if 대신 조건부 연산자 ?를 사용하면 코드를 더 간결하고 읽기 쉽게 만들 수 있다.
function sumTo(num) {
  return (num<=1) ? num : (num + sumTo(num-1));
}

재귀는 언제 사용하는 게 좋을까?

주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

모든 재귀 함수는 반복문(while 문 또는 for 문)으로 표현할 수 있다. 그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽다.

재귀적 사고 연습하기

arrSum을 예시로 연습해보자.

재귀 함수의 입력값과 출력값 정의하기
-> 재귀적으로 사고하는 데에 가장 먼저 해야할 일은 문제를 가장 추상적으로 또는, 가장 단순하게 정의하는 것

함수 arrSum의 경우 number 타입을 요소로 갖는 배열을 입력받고, number 타입을 리턴

arrSum: [number] => number

문제를 쪼개고 경우의 수를 나누기
-> 주어진 문제를 어떻게 쪼갤 것인지 고민한다. 문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인한다.
일반적인 경우, 입력값을 기준을 정한다. 이때 중요한 관점은 입력값이나 문제의 순서와 크기다.

함수 arrSum 의 경우 입력값인 배열의 크기에 따라, 더 작은 문제로 나눌 수 있다.
그리고 arrSum([1, 2, 3, 4]) 를 구하는 방법과 arrSum([2, 3, 4]) 을 구하는 방법은 같다.
이제 문제에서 주어진 입력값에 따라, 경우의 수를 나눠보자. 
일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눈다.

함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있다. 
각각의 경우는 다른 방식으로 처리해야 한다.

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

단순한 문제 해결하기
-> 가장 해결하기 쉬운 문제부터 해결한다. 이를 재귀의 기초(base case)라고 말한다.
재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성한다.

함수 arrSum 을 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고
  , 이때 arrSum([]) 의 리턴값은 0이다.

arrSum([ ]) = 0;

복잡한 문제 해결하기
-> 남아있는 복잡한 경우를 해결하자.

길이가 1 이상인 배열이 함수 arrSum 에 입력된 경우, 맨 앞의 요소에 대한 결과를 따로 구하고
(배열의 맨 앞의 요소니까 head라고 이름 붙여보자.)
  , 나머지 요소를 새로운 입력값으로 갖는 문제로 구분하고, 이에 얻은 결과를 head에 더해준다.
  
arrSum: [number] => number
arrSum([ ]) = 0;
arrSum([e1, e2, ... , en]) = e1 + arrSum([e2, ..., en])

배열을 head와 나머지 부분(tail)으로 구분할 수 있다면, 함수 arrSum을 재귀적으로 구현할 수 있다 !

코드 구현하기

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, ...)
}

팩토리얼 계산하기

팩토리얼은 num이 자연수일 때, 1부터 n까지의 모든 자연수의 곱을 의미한다.

재귀의 베이스를 0으로 잡아줌.
fuction factorial(num) {
  return num ? num * factorial(num-1) : 1;
}

1일 경우
function factorial(num) {
  return (num != 1) ? num * factorial(num-1) : 1;
}

피보나치 수 계산하기

피보나치 수는 첫째와 둘째항이 1이고, 그 뒤의 모든 항은 바로 앞 두항의 합인 수열.
Fn = Fn-1 + Fn-2

function fibonacci(num) {
  return (num <=1 ) ? num : fibonacci(num-1) + fibonacci(num-2);
}

yezo cha