재귀함수 21.03.25

in Dev on Java Script


재귀 함수

재귀 (Recursion) : 자신을 정의할 때 자기 자신을 재 참조하는 방법 이를 프로그래밍에 적용한 재귀 호출(Recursive call)의 형태로 많이 사용된다. (fractal이랑 비슷)

재귀 함수 (Recursion Function) : 함수에서 자신을 다시 호출(재귀 호출)하여 작업을 수행하는 방식의 함수.

재귀 함수 꼭 기억해야할 점

  • 함수 내에서 재귀 호출 후 호출 한 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다. 함수 종료 후 이후의 명령문은 수행되어야한다.

  • 종료 조건(Base Case)이 꼭 포함되어야 한다는 부분을 인지하고 작성하면 무한 루프를 방지 가능

재귀 함수를 사용해야하는 경우

  • 주어진 문제가 (구조는 비슷하고) 더 작은 문제로 나뉘어 질 수 있는 경우

  • 중첩된 루프가 많거나 중첩의 정도(number of loops)를 미리 알 수 없는 경우

재귀적으로 사고하는 방법

  1. 재귀 함수의 입력 값과 출력값 정의하기 문제를 가장 추상적으로 또는 가장 단순하게 정리하기.

ex) arrSum의 경우 number 타입을 요소로 갖는 배열을 입력으로 받아서 number를 리턴합니다.

arrSum: [number] => number
  1. 문제를 쪼개고 경우의 수를 나누기

주어진 문제를 어떻게 쪼갤 것인지 고민합니다. 어떤 기준을 정하고 그 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는 지 검토해봅니다. 일반적으로 입력값이 이 기준을 정하는 대상이 됩니다. 이 때 중요한 관점은 순서와 크기입니다. 주어진 입력값 또는 문제 상황을 크기를 기준으로 구분할 수 있거나, 순서를 명확하게 정할 수 있는지를 살펴보는 것이 도움이 됩니다.

ex)

arrSum의 경우 입력값인 배열을 배열의 크기에 따라 구분할 수 있습니다. 
그리고 arrSum([1, 2, 3, 4])를 구하는 방법과 arrSum([2, 3, 4])을 구하는 방법은 동일.
이 구분은 적절하다고 판단할 수 있습니다.

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

arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있습니다. 
각각의 경우는 다르게 처리되어야 합니다.

arrSum: [number] => number
arrSum([ ])
arrSum([e1, e2, ... , en])
  1. 단순한 문제 해결하기 문제를 여러 경우로 구분한 다음에는 쉬운 문제부터 해결합니다. 이를 재귀의 기초(base case)이라고 부릅니다.

재귀의 기초는 나중에 재귀 함수 구현 시 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성하게 됩니다.

arrSum를 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이 때 arrSum은 0입니다.

arrSum: [number] => number
arrSum([ ]) = 0
arrSum([e1, e2, ... , en])
  1. 복잡한 문제 해결하기
arrSum이 길이가 1 이상인 배열을 입력으로 받을 경우, 
맨 앞의 요소를 따로 구하고(배열의 맨 앞의 요소이기 때문에 head라고 이름 붙이겠습니다.),
나머지 요소를 새로운 입력값으로 갖는 문제를 해결하여 얻은 결과를 head에 더합니다.

arrSum: [number] => number
arrSum([ ]) = 0
arrSum([e1, e2, ... , en]) = e1 + arrSum([e2, ..., en])

배열이 있을 때 head와 나머지 부분(tail)을 구분하는 방법만 안다면, arrSum을 해결할 수 있습니다.

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

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

function rec(param1, param2) {
    // 재귀의 기초 (base case) : 재귀 함수 종료(탈출)
    if (some_codition){
        return;
    }
    // Reculsive Case
    if (some_condition) {
        rec(param1, param2)
    } else {

    }
}

rec(param1, param2)

// 함수는 실행 된 후 함수로 돌아온다.
// 함수가 끝나는 경우 body에 있는 코드를 다 실행하거나, return을 만나는 경우
fibo(4)가 끝나기 전까지 fibo(3)은 실행되지 않는다
1.fibo(5) = fibo(4) + fibo(3)
2.fibo(4) = fibo(3) + fibo(2)
3.fibo(3) = fibo(2) + fibo(1)
4.fibo(2) = fibo(1) + fibo(0)

----
fibo(3)
fibo(2) = fibo(1) + fibo(0)

재귀 호출 된 함수가 return 되도 이전 함수의 실행안된 부분을 실행해야한다!

재귀 호출 된 함수가 return 되면 해당 함수가 종료되지, 이전 함수의 나머지 부분이 종료되지않는다. 재귀 호출이 종료되면 이전 함수로 돌아와서 재귀 함수 뒷부분을 실행해줘야한다! (for 문에서 return이 나오면 전체 함수가 종료)

[더 공부해야할 사항]

  • 하노이의 탑과 조합(combination) 문제를 재귀와 그렇지 않은 경우
  • 꼬리 재귀
  • 꼬리 물기 최적화

알고리즘 문제 TIP

  • 배열은 head와 tail을 통해 재귀적으로 정의될 수 있다.
let head = arr[0];
let tail = arr.slice(1)
// tail은 arr의 첫 엘리먼트를 제외한 나머지

=

[head, ...arr] = arr
// spead syntax를 통해 head tail 구하기



© 2020.11. by creamer

Powered by CREAMer