재귀
재귀(再歸) : 원래의 자리로 되돌아 가거나 되돌아옴
function recursion() { console.log("This is") console.log("recursion!") recursion() }위의 함수를 호출하면
자기 자신을 끝없이 호출하면서 같은 코드가 계속 실행된다
"자기 자신을 호출하는 함수 = 재귀함수"
재귀로 문제 해결
문제: 자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수 arrSum 을 작성하세요.
ex)arrSum 함수로 배열 [1, 2, 3, 4, 5] 의 합을 구하는 과정
1. 문제를 작게 쪼개기
배열의 합을 구할때[1, 2, 3, 4, 5]의 합을 구하는 것보다[2, 3, 4, 5]의 합을 구하는 것이 더 작은 문제이고,[3, 4, 5]의 합을 구하는게 더 작은 문제가 된다.
2. 문제를 가장 작은 단위로 쪼개기
방법 1의 단계를 반복해서 쪼개면 더이상 쪼갤 수 없는 상태에 도달하게 된다.
마지막에는 빈 배열을 받게 되고 더이상 쪼갤 수 없게 된다.
"문제를 가장 작은 단위로 쪼갰다"
3. 문제 해결하기
문제가 더이상 쪼개지지 않게 되면 가장 작은 단위의 문제를 해결한다.
2단계에서 도달한 가장 작은 문제는arrSum([])이었다. 빈 배열의 합은 0이기때문에 0을 리턴해 주면 된다.
가장 작은 문제를 해결하는 순간, 아래의 코드와 같이 쪼개졌던 문제가 거꾸로 올라가면서 합쳐지게 된다.
재귀는 언제 사용하면 좋을까?
1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우
"재귀를 적용할 수 있는 대부분의 경우는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽다"
재귀적으로 사고하기
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. 단순한 문제 해결하기
문제를 여러 경로로 구분한뒤, 가장 해결하기 쉬운 문제부터 해결!
➡️ 재귀의 기초(base case) : 재귀의 탈출 조건(재귀호출이 멈추는 조건)구성
함수 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]) ← 그렇지 않은 경우 : 해결!
5. 코드 구현하기재귀 템플릿
출처, 참조 : 코드스테이츠
