자바스크립트_재귀함수 기본 개념정리_다르게 생각하기

오늘은 재귀함수에 대해 알아보도록 하겠습니다.

재귀함수는 어떤 함수가 자기 스스로를 호출하는 것을 말합니다.

자기 자신을 호출하는 함수로 조건이 충족될때까지 반복적으로 함수를 불러내면서 주어진 작업을 수행하는 것을 의미합니다.

5! = factorial(5)이라는 함수가 있습니다.

우리는 이것을

=5*4*3*2*1 가 될 것을 알고 있습니다.

이건 이렇게도 표현이 가능합겁니다.

=5*4!

=5*4*3!

=5*4*3*2!

=5*4*3*2*1!

 

우리는 지금 구조가 비슷하다는 걸 알수있고, 어떤 문제를 해결할때 같은 구조를 가진 문제를 해결하는 방법을 재귀라고 합니다.

재귀는 다음과 같은 상황에 적합하게 사용됩니다.

1. 주어진 문제가 (구조는 비슷하고) 더 작은 문제로 나뉘어 질 수 있는 경우
2. 중첩된 루프가 많거나 중첩의 정도(number of loops)를 미리 알 수 없는 경우

재귀함수는 이러한 기본형태를 가집니다.

function recursive(인자) {
작업수행
if(조건충족){
return 결과
    } else {
     return recursive(작업된 인자)
   }
}

위에 들었던 예시인 팩토리얼을 계산하는 함수는 위의 기본형태를 바탕으로 이렇게 만들어집니다.

function fac(n) {
  if(n===1) return 1
   else return n * fac(n-1)
}

n이 1이 되면 멈추는 조건을 만들어줍니다.

아니라면 n* 다음 팩토리얼의 함수를 n-1의 수로 반복하게 됩니다.

재귀함수를 하면 하노이의 탑 예시가 많이 나옵니다.

하노이의 탑의 코드는 이런 형태가 됩니다. 

function hanoi( num ,  from , to , other ){
  if (num === 0 ) return;
  hanoi ( num -1 , from , other , to );
    console.log(`${from}번에서 ${to}로 옮긴다.`);
  hanoi ( num-1 , other , to , from );
}

여기서 원반갯수는 num,

출발지 기둥번호는 from,

목적지 기둥번호는 to,

나머지 기둥번호는 other 입니다.

 console.log를 찍어보게 되면 다음과 같이 나옵니다.

 

재귀적으로 사고하기 위해서는 4가지를 생각해봐야합니다.

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

재귀 함수를 통해 어떤 문제를 풀고자 할때, 가장 추상적으로 또는 단순하게 정리해야 합니다.

 

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

어떤 기준을 정하고 그 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는 지 검토해야합니다.

이 때의 기준은 순서와 크기 입니다. 주어진 입력값 또는 문제 상황을 크기를 기준으로 구분할 수 있거나, 순서를 명확하게 정할 수 있는지를 살펴보는 것이 중요합니다.

 

3. 단순한 문제 해결하기

문제를 여러 경우로 구분한 다음엔 쉬운 문제부터 해결해 나갑니다. 이를 재귀의 기초 base case라고 합니다. 

 

4. 복잡한 문제 해결하기

단순한 문제를 하나씩 해결해나간다음 복잡한 문제에 접근하여 해결합니다.

 

 

 

오늘은 재귀함수의 개념과 재귀적 사고하는 방법에 대해 알아보았습니다. 읽어주셔서 감사합니다.