재귀
재귀의 이해
재귀 : 원래의 자리로 되돌아가거나 되돌아옴
재귀 코드
function recursion () {
console.log("This is")
console.log("recursion!
")
recursion()
}
재귀() 함수?
같은 코드를 반복해서 실행하고 끝없이 자신을 호출합니다.
이렇게 자신을 호출하는 함수 재귀 함수말하다
재귀로 문제 해결
문제 : 자연수로 이루어진 리스트(배열)을 입력받고, 리스트의 합을 리턴하는 함수 'arrSum'을 작성하세요.
1. 문제를 더 작은 조각으로 나눕니다.
(1, 2, 3, 4, 5)의 합을 구하는 과정.
1 + 2 + 3 + 4 + 5 =?
2 + 3 + 4 + 5 =?
3 + 4 + 5 =?
4 + 5 =?
…
위의 문제는 코드로 분류됩니다.
arrSum((1, 2, 3, 4, 5)) === 1 + arrSum((2, 3, 4, 5))
arrSum((2, 3, 4, 5)) === 2 + arrSum((3, 4, 5))
...
2. 문제를 가장 작은 단위로 분해
...
arrSum((3, 4, 5)) === 3 + arrSum((4, 5))
arrSum((4, 5)) === 4 + arrSum((5))
arrSum((5)) === 5 + arrSum(()) // 더 이상 쪼갤 수 없는 상태
3. 문제 해결
가장 작은 문제를 해결하여 전체 문제 해결
arrSum(()) === 0; // <-- 가장 작은 문제를 빈 배열의 합 0으로 리턴
// 가장 작은 경우의 해결책을 적용합니다.
arrSum((5)) === 5 + arrSum(()) === 5 + 0 === 5;
arrSum((4, 5)) === 4 + arrSum((5)) === 4 + 5 === 9;
arrSum((3, 4, 5)) === 3 + arrSum((4, 5)) === 3 + 9 === 12;
arrSum((2, 3, 4, 5)) === 2 + arrSum((3, 4, 5)) === 2 + 12 === 14;
arrSum((1, 2, 3, 4, 5)) === 1 + arrSum((2, 3, 4, 5)) === 1 + 14 === 15;
코드 작성
function arrSum (arr) {
// 빈 배열을 받았을 때 0을 리턴하는 조건문
// --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
if (arr.length === 0) {
return 0
}
// 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
// --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
return arr.shift() + arrSum(arr)
}
재귀의 예
하나. 주어진 문제는 유사한 구조의 더 작은 문제로 나눌 수 있습니다.
2. 중첩 루프가 많거나 루프 수를 예측하기 어려운 경우
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);
}
}
}
}
}
}
}
}
재귀 사용
재귀적으로 생각하다
1. 재귀 함수의 입력과 출력 정의
추상적이거나 가장 간단하게 정의된
함수의 입출력 값 정의 -> 재귀함수로 대상 정의
2. 문제를 세분화하고 사례 수를 나눕니다.
문제를 구분하는 기준을 정하고 정해진 기준에 따라 문제를 큰 경우와 작은 경우로 나눈다.
분류 기준은 “입력 또는 문제의 순서 및 크기” 오전
3. 간단한 문제 풀기
문제를 여러 경우로 나눈 다음 가장 간단한 문제를 먼저 해결합니다.
재귀의 기초
재귀의 기본은 나중에 재귀 함수를 구현할 때 재귀의 초기 조건(재귀 호출이 중지되는 조건)입니다.
탈출 조건이 없다면? 끝이 없다
4. 복잡한 문제 해결
나머지 복잡한 경우 해결
5. 코드 구현