intro
再歸(다시 돌아오다)
Lesson - 재귀 함수
-
재귀의 의미에 대해서 이해하고, 자바스크립트에서 재귀 호출을 할 수 있다.
-
재귀를 언제 사용해야 하는지 알고 있다. => 알고리즘 표현에서 재귀적인 표현이 자연스러울때 . 주의해야 할 점은 입력값의 변화가 없거나 입력값이 특정 패턴을 반복하게 되면 영원히 반복되다가 콜 스택 에러로 뻗어버리게 되므로 입력값이 종료 조건으로 수렴하는지 판단해야 한다.
-
재귀적 사고 연습을 통해 재귀 함수를 base case와 recursive case로 나눠서 작성할 수 있다. => base case 기반조건 recursive case: 재귀 조건
-
재귀 함수의 활용 (트리 구조)
- 트리 구조에 재귀 함수를 활용
- JSON 구조에 재귀 함수를 활용
- DOM 구조에 재귀 함수를 활용
-
자료 구조 중 Tree 구조에 재귀 함수를 사용하는 이유를 이해할 수 있다.
- 실생활에 사용되는 유용한 Tree 구조를 알고 있다. => 최단 경로 BPS
- 깊이를 알 수 없는 Tree 구조에 재귀 함수를 활용하여 모두 순회(traverse)할 수 있다
재귀의 이해 - 다르게 생각하기
Q) 자연수로 이루어진 배열을 입력받고, 리스트의 합을 리턴하는 함수 'arrSum'을 작성하라.
Ex1) 나의 정답
function arrSum(arr) {
let result = 0;
for (let i = 0; i < arr.length; i++) {
result += arr[i];
}
return result;
}1. result를 0으로 초기화함
2. i = 0 부터 순서대로 배열의 구성요소에 접근하며 result에 더한다.
그런데?
이 문제를 다른 각도에서 생각해 보자
문제를 쪼개서 생각하는 방법
어떤 문제를 해결할 때, 동일한 구조의 더 작은 문제를 해결함으로써 주어진 문제를 해결하는 방법을 재귀(recursion)라고 함.
예를 들어 [10, 3, 6, 2] 를 다 더하고 싶을때
1. 기존의 문제에서 출발하여 더 작은 경우를 생각함.10, 3, 6, 2를 더하는것 보다 우선 3, 6, 2를 더하고 10을 더하는게 나음!
arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2])2. 같은 방식으로, 문제가 더는 작아지지 않을 때까지 더 작은 경우 반복 확인
arrSum([3, 6, 2]) = 3 + arrSum([6, 2]);
arrSum([6, 2]) = 6 + arrSum([2]);
arrSum([2]) = 2 + arrSum([]);3. 문제가 간단해진 순간부터 차례로 거슬러 올라가서 해결
arrSum([]) = 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용한다.
arrSum([2]) = 2 + arrSum([]) = 2;
arrSum([6, 2]) = 6 + arrSum([2]) = 6 + 2 = 8;
arrSum([3, 6, 2]) = 3 + arrSum([6, 2]) = 3 + 8 = 11;
arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]) = 10 + 11 = 21;
// 정리 ver.
/*
* 1. arr이 빈 배열인 경우 = 0
* 2. 그 외의 경우 = arr[0] + arrSum(arr2)
* (arr2는 arr의 첫 요소를 제외한 나머지 배열)
*/
arrSum(arr);재귀 호출 : 함수 실행과정 중에 자기 자신을 호출하는 것
재귀는 언제 사용하는 게 좋을까?
1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우
모든 재귀 함수는 반복문으로 표현은 가능
근데 반복문이 너무 복잡할때 재귀 함수로 깔끔하게 정리 가능!
재귀적 사고 연습하기
재귀는 자전거를 타는 것이랑 비슷함.
처음 배울 떄, 다른 사람이 타는 것을 지켜보면 저거저거 꽤 쉽네 하는데
막상 내가 타려하면 안타짐...ㅠ
그냥 계속 시도하고 연습해야함!
그래서 재귀적 사고 가이드라인을 적는다!
재귀적 사고 가이드 라인
1. 재귀 함수의 입력값과 출력값 정의하기
재귀 함수를 통해 도달하고자 하는 목표를 우선 정의하자!
예를 들어 arrSum의 경우 number 타입을 요소로 갖는 배열이 입력값, numer 타임을 리턴하는게 출력값!
2-1 . 문제를 쪼갠다!
그럼 문제를 쪼개는 기준은!?
입력값이나 문제의 순서와 크기가 기준!
또한 구분된 문제를 푸는 방식이 순서나 크기에 관계 없이 모두 같아면 문제를 제대로 구분한 것!
ex) arrSum([1, 2, 3, 4]) 를 구하는 방법과 arrSum([2, 3, 4]) 를 구하는 방법이 동일함! -> 적절...하다!
2-2. 쪼갠것들의 경우의 수를 나눔!
arrSum: [number] => number
arrSum([ ]) // 빈 배열을 입력값으로 받을 경우
arrSum([e1, e2 ... , en]) // 빈 배열이 아닐 경우3. 단순한 문제 해결하기!
가장 해결하기 쉬운 문제부터 해결 => 이를 재귀의 기초!
재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건을 구성!
- 함수 arrSum을 더 이상 쪼갤 수 없는 경우 입력값이 빈 배열일 경우이고, 이떄 arrSum([ ]) 의 리턴값은 0.
4. 복잡한 문제 해결하기.
- 길이가 1 이상인 배열이 함수 arrSum에 입력된 경우, 맨 앞의 요소에 대한 결과를 따로 구하고
나머지 요소를 새로운 입력값으로 갖는 문제로 구분하고, 이를 해결하여 얻은 결과를 head에 더함.
arrSum([e1, e2, ... , en]) = e1 + arrSum([e2, ... , en])5. 코드 구현하기.
function recursive(input1, input2, ...) {
// Base Case : 문제를 더 이상 쪼갤 수 없는 경우
if (문제를 더 이상 쪼갤 수 없을 경우) {
return 단순한 문제의 해답;
}
// recursive Case
// 그렇지 않은 경우
return 더 작은 문제로 새롭게 정의된 문제
// 예1. someValue + recursive(input1Changed, input2Changed, ...)
// 예2. someValue * recursive(input1Changed, input2Changed, ...)
}my tip) 뭔가 head tail 부분을 잘 조절하면 될 것 같다!
재귀 함수의 중요한 3가지 특성
1. 종료 조건
if (나쁜 값) { 정지 }
2. 기반 조건(Base case, 기저 상태)
if (이런 일이 일어난다면) { 성공 }
3. 재귀
재귀 함수에 관한 예제
Q1. 팩토리얼
function factorial(x) {
if (x<0) return;
if (x===0) return 1;
return x * factorial(x-1);
}
factorial(3);
// 61. 종료 조건
if ( x < 0) return;
2. 기반 조건
if ( x === 0) return 1;
3. 재귀
return x * factorial ( x - 1)
Q2. 자바스크립트에서 문자열을 뒤집는 방법
function revStr(str) {
if (str === '') return '';
return revStr(str.substr(1)) + str[0];
}
revStr('cat')
// tac1. 종료 조건 : x
2. 기반 조건 : str === ""
3. 재귀 : return rev(str.substr(1)) + str[0]
