230213 - 재귀

1. 재귀(Recursion)

재귀란?

재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴.

 

재귀 함수 : 자기자신을 호출하는 함수. 반복적인 작업을 해야하는 문제를 더 간결하게 풀어낼 수 있다. 

 

1) 재귀로 문제 해결하기

• 문제를 작게 쪼갠다.
• 위와 같이 문제가 더는 작아지지 않을때까지 가장 작은 단위로 문제를 쪼갠다.
• 가장 작은 단위의 문제를 풂으로써 전체적인 문제를 해결한다. 

 

2) 재귀는 언제 사용하나? 

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

모든 재귀함수는 반복문(for/while)으로 표현할 수 있다. 하지만 재귀를 적용할 수 있는 대부분의 경우 재귀를 적용하는 코드가 훨씬 간결하고 이해하기 쉽다. 

 

 

3) 재귀의 활용

입력받은 수의 팩토리얼을 리턴하는 재귀함수 fac을 구현해야한다고 가정하자. 

 

1. 재귀 함수의 입력값과 출력값 정의하기 

재귀적으로 사고하기 위해 가장 먼저 해야하는 일은 문제를 가장 추상적 또는 단순하게 정의하는 것이다.

따라서 함수의 입력값과 출력값을 먼저 정의해 두면 풀어야하는 문제의 최종 목표를 정의하는데 도움이 된다. 

 

함수 fac의 경우, number 타입의 값을 입력값으로 하고, number 타입의 값을 리턴한다. 

 

 

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

문제를 쪼갤 기준을 정하고 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인한다. 

일반적으로는 입력값을 이 기준으로 정한다. 이때 중요한 것은 입력값이나 문제의 순서와 크기이다. 

구분된 문서를 푸는 방식이 순서나 크기와 관계없이 모두 같다면 문제를 제대로 구분한 것이다. 

 

이후 문제에서 주어진 입력값에 따라 경우의 수를 나눈다. 일반적으로 문제를 더이상 쪼갤수없는 경우와 그렇지 않은 경우로 나눈다. 

 

함수 fac의 경우, 이렇게 문제를 쪼갤 수 있다. 

fac(5) = 5 * 4 * 3 * 2 * 1;
fac(4) = 4 * 3 * 2 * 1;
fac(3) = 3 * 2 * 1;
fac(2) = 2 * 1;
fac(1) = 1;

 

 

3. 단순한 문제 해결하기(base case)

여러 경우로 문제를 구분한 다음 가장 해결하기 쉬운 문제부터 해결한다. => 재귀의 기초(base case)

재귀의 기초는 나중에 재귀함수 구현시 재귀의 탈출 조건(재귀 호출이 멈추는조건)이 된다. 

탈출 조건이 없는 경우 재귀함수는 끝없이 자기 자신을 호출하고, 문제를 덜 쪼갠 상태에서 탈출 조건을 세우는 경우 문제를 제대로 해결할 수 없다. 그러므로 문제를 최대한 작게 쪼갠 후 문제를 해결해야 한다. 

 

함수 fac의 경우, fac의 인자가 1이거나 0이면 재귀의 탈출 조건인 base case가 된다. 따라서 이렇게 표현할 수 있다. 

// base case
if (num <= 1) return 1;

 

 

4. 복잡한 문제 해결하기(recursive case)

남아있는 복잡한 경우를 해결한다. 

 

함수 fac의 경우, 이렇게 표현할 수 있다. 

// 각각의 fac()은 다음과 같이 바꿔쓸 수 있다.
fac(5) = 5 * fac(4);
fac(4) = 4 * fac(3);
fac(3) = 3 * fac(2);
fac(2) = 2 * fac(1);

 

 

5. 코드로 작성하기 

정리한 내용을 코드로 작성한다.

 

function fac(num) {
    if (num <= 1) return num;

    return num * fac(num - 1) 
}

 

 

 

✅ 일반적인 재귀 함수의 템플릿 

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

 

 

 

 

 

 

*****************

 

재귀함수 진짜 어렵다 흑흑 

일단은 연습문제들 다시 다 풀어볼생각이다