[ 알고리즘 기법 ] 재귀 함수 개념 / 재귀 알고리즘 기법 정리

재귀의 뜻

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

 

재귀 함수 

• 자기 자신을 호출하는 함수

 

자기 자신을 호출하는걸 어떻게 한다는거졍;?

 

코드로 봅시다.

function name () {
  console.log("my name is")
  console.log("myossi")
  name()
}

console.log(name())

위의 name 함수를 콘솔로그로 호출했을때 아래와 같은 결과를 볼 수 있음

my name is
myossi
my name is
myossi
my name is
myossi
my name is
myossi
my name is
myossi

name 함수 안에서 name() 함수, 즉 자기 자신을 호출하게 되면 끊임 없이 반복해서 name함수 안의 로직이 실행된다.

 

그럼 재귀는 언제 사용되는지 대충 감이 오시져?

 

걍 반복문 쓰면 되는거 아닌감;

for문을 이용해서 해결할 문제는 풀립니다.

하지만,  for문을 이용했을 때 아래 코드가 됩니다.

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
            for (let l = 0; l < n; l++) {
                for (let m = 0; m < n; m++) {
                    for (let n = 0; n < n; n++) {
                        for (let o = 0; o < n; o++) {
                            for (let p = 0; p < n; p++) {
                                // do something
                                someFunc(i, j, k, l, m, n, o, p);
                           }
                        }
                    }
                }
            }
        }
    }
 }

 

 

반복문과 재귀의 차이는 반복문이 재귀보다 성능적인 면에서 메모리나 속도 등이 높다고 한다.

따라서 , 위의 코드와 같이 중첩된 반복문이 많거나 중첩 횟수가 예측하기 정말 어려운 경우 재귀를 사용하는 것이 맞는 것 같다.

 

재귀는 언제 사용될까요

• 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
• 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우
• 반복문으로 작성된 코드를 더욱 간결하고 이해하기 쉽게 작성하고 싶은 경우

 

 

재귀의 기본 형식

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

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

• 재귀의 탈출 조건(재귀 호출이 멈추는 조건)이 구성되어야 한다.
• 탈출 조건이 구성되어 있지 않으면 자기 자신을 호출하는 순간 끊임없이 반복된다.

base case : 문제를 더 이상 쪼갤 수 없는 경우

• 재귀의 조건이 구성되어야 한다.
• 탈출 조건의 반대의 경우 -> 반복해서 자기 자신을 호출해서 할 일 이라고 생각하면 된다.

recursive case : 그렇지 않은 경우

 

재귀를 사용할 때 , 재귀적 사고를 더욱 쉽게 할 수 있는 가이드를 알아보자.

 

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

함수 arrSum 의 경우 number 타입을 요소로 갖는 배열을 입력으로 받고, number 타입을 리턴
이를 좀 더 간단하게 표기하면 다음과 같다.

arrSum: [number] => number ← 입출력 값 정의

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

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

함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있다. 
각각의 경우는 다른 방식으로 처리해야 한다.
arrSum: [number] => number
arrSum([ ]) ← 입력값이 빈 배열인 경우
arrSum([요소1, 요소2, ... , 요소n]) ← 그렇지 않은 경우

3. 단순한 문제 해결하기

함수 arrSum 을 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 
이때 arrSum([]) 의 리턴값은 0이다.
arrSum: [number] => number
arrSum([ ]) === 0 ← 입력값이 빈 배열인 경우 : 해결!
arrSum([요소1, 요소2, ... , 요소n])

4. 복잡한 문제 해결하기

길이가 1 이상인 배열이 함수 arrSum에 입력된 경우, 
입력된 배열을 배열의 첫 요소와 나머지 요소를 입력값으로 갖는 문제로 쪼개고, 둘을 더한다.
arrSum: [number] => number
arrSum([ ]) === 0
arrSum([요소1, 요소2, ... , 요소n]) === 요소1 + arrSum([요소2, ..., 요소n]) ← 그렇지 않은 경우 : 해결!
배열을 첫 요소와 더 작은 문제로 쪼개는 방법만 안다면, 함수 arrSum 을 재귀적으로 구현할 수 있다.

5. 코드 구현

function arrSum(arr) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr의 길이가 0인 경우) {
    return 0;
  }

  // recursive case : 그렇지 않은 경우
  return 요소1 + arrSum([요소2, ... , 요소n]);
}

 

재귀 알고리즘 문제 기본 예제

문제 : 자연수를 입력받고, 입력받은 수부터 1까지의 자연수를 모두 곱한 값을 리턴하는 재귀 함수 `fac` 을 작성하세요.

위 문제에 맞게 재귀를 사용한 코드

function factorial(num) {
// 재귀 탈출 조건 : 1이 되면 *연산은 끝이 난다.
  if (num === 1) return 1
// num이 1이 될때까지 재귀를 함
  return num * factorial(num -1)
}

factorial(5)

계산되는 형식은 아래와 같다.

회차	연산	결과
1	num  *  factorial(num -1) 5 *  factorial(5-1)	5
2	num  *  factorial(num -1) 5 * 4 *  factorial(4-1)	20
3	num  *  factorial(num -1) 5 * 4 * 3 * factorial(3-1)	60
4	num  *  factorial(num -1) 5 * 4 * 3 * 2 *  factorial(2-1)	120

결론적으로, factorial 함수를 실행했을 때 120을 return 받는다.