❤️🔥 재귀란?
- 재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴
🤔 JavaScript에서 재귀란 어떤 형태일까?
function recursion(){
recursion();
}- 다음과 같이 recursion이라는 함수 안에서 자기 자신인 recursion 함수를 다시 되돌아가서 호출하는 모양을 나타낸다.
🤔 재귀를 활용하여 문제 해결하기
문제: 자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수
arrSum을 작성하세요.
🤔 재귀는 언제 사용하면 좋을까?
- 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
- 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우
- 반복문으로 작성된 코드를 더욱 간결하고 이해하기 쉽게 작성하고 싶은 경우
❤️🔥 재귀의 활용
💡 재귀적으로 사고하기
🔹 재귀 함수의 입력값과 출력값 정의하기
재귀적으로 사고하기 위해서는 문제를 추상적, 단순하게 정의하는 것이다. 함수의 입출력값을 정의하여 재귀 함수를 통해 풀고자하는 문제, 도달하고자 하는 목표를 정의하는 데에 도움이 된다.
arrSum : [number] => number
arrSum은 number 타입을 요소로 가지는 배열을 입력으로 받고 있으며, number 타입을 리턴한다.🔹 문제를 쪼개고 경우의 수 나누기
문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우, 작은 경우로 구분할 수 있는지 확인한다. 일반적으로 입력값을 이 기준으로 정하게 되는데, 이때 중요한 관점은 입력값이나 문제의 순서와 크기이다. 주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분하는 데에 도움이 된다.
arrSum의 경우 입력값인 배열의 크기에 따라, 더 작은 문제로 나눌 수 있다.
또한 arrSun([1, 2, 3, 4])를 구하는 방법과 arrSum([2, 3, 4])를 구하는 방법은
계속 동일하므로 구분이 적절함을 알 수 있다.
arrSum: [number] => number
arrSum([ ]) ← 입력값이 빈 배열인 경우
arrSum([요소1, 요소2, ... , 요소n]) ← 그렇지 않은 경우🔹단순한 문제 해결하기
재귀의 기초: 문제를 여러 경우로 구분한 다음, 가장 해결하기 쉬운 문제부터 해결, 재귀의 탈출 조건을 먼저 구성한다. 만약 탈출 조건 없이 자기 자신을 호출하게 된다면 계속해서 자기 자신(함수)를 호출하게 되므로 무한루프를 돌게 된다. 탈출 조건을 구성 후, 문제를 최대한 작게 쪼갠 후 문제를 해결하는 것이 중요하다.
arrSum: [number] => number
arrSum([ ]) === 0 ← 입력값이 빈 배열인 경우 : 해결!
arrSum([요소1, 요소2, ... , 요소n])🔹복잡한 문제 해결하기
남아 있는 복잡한 경우를 해결
길이가 1 이상인 배열이 함수 arrSum 에 입력된 경우,
입력된 배열을 배열의 첫 요소와 나머지 요소를 입력값으로 갖는 문제로 쪼개고, 둘을 더합니다.
arrSum: [number] => number
arrSum([ ]) === 0
arrSum([요소1, 요소2, ... , 요소n]) === 요소1 + arrSum([요소2, ..., 요소n]) ← 그렇지 않은 경우 : 해결!
배열을 첫 요소와 더 작은 문제로 쪼개는 방법만 안다면, 함수 arrSum 을 재귀적으로 구현할 수 있다.🔹코드 구현하기
[일반적인 재귀 함수 템플릿]
function recursive(input1, input2, ...) {
// base case : 문제를 더 이상 쪼갤 수 없는 경우
if (문제를 더 이상 쪼갤 수 없을 경우) {
return 단순한 문제의 해답;
}
// recursive case : 그렇지 않은 경우
return 더 작은 문제로 새롭게 정의된 문제
}❤️🔥 예제 | 재귀를 활용해 factorial 풀기
function fac(num){
if(num === 1){
return 1;
}
return num * fac(num-1);
}
fac(5)
