재귀란?
- 원래의 자리로 되돌아가거나, 되돌아오는 것
- 자기자신을 호출하는 절차
재귀함수
재귀함수는 종료조건이 있어야 하며, 종료조건을 설정해주지 않으면 무한 반복을 하게된다. 재귀함수로 작성이 되는 코드는 반복문으로도 작성할 수 있다.
- 자기자신 호출시 스택영역에 계속누적됨.
재귀 함수의 필수 요소
문제를 같은 형태의 더 작은 문제로 쪼개야 하기 때문에 패턴을 찾아야 한다
탈출,종료 조건(base case, base condition)
- 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야하한다
- 탈출 조건(base case)이 없는 경우, 무한반복되어 스택 오버플로우 현상 발생
base case(탈출조건): 더 이상 문제를 쪼갤 필요가 없는 경우
recursive case: 문제를 쪼개서 풀어가는 경우
recursive case
- 순환을 반복하다보면 결국 base case로 수렴해야한다
탈출조건이 없는경우,
- 끝없이 자기자신호출,최대한 작게쪼갠후 문제해결하는것 중요
문제 예시
자연수로 이루어진 리스트(배열)를 입력받고,
리스트의 합을 리턴하는 함수arrSum을 작성하세요.
// 배열 [1, 2, 3, 4, 5])
- 문제를 작게 쪼개기
//합을 구하는 과정을 작게 쪼개기
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5])
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5])
arrSum([3, 4, 5]) === 3 + arrSum([4,5])
arrSum([4, 5]) === 4 + arrSum([5])
...- 문제를 가장 작은 단위로 쪼개기
//arrSum 이 빈 배열을 받게되면서 문제를 더이상 쪼갤 수 없는 상태
...
arrSum([5]) === 5 + arrSum([])- 문제 해결하기
arrSum([]) === 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;
// return arrSum; = 5
//arrSum 함수의 리턴값이 나오면서 연쇄적으로 문제가 해결되고,
//최종적으로는 문제 전체가 해결되는 것을 볼 수 있다.function arrSum (arr) {
// 빈 배열을 받았을 때 0을 리턴하는 조건문
// --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
if (arr.length === 0) {
return 0
}
// 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
// --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
return arr.shift() + arrSum(arr)
}
arrSum 함수가 내부에서 arrSum 함수를 호출하면서 문제가 쪼개어져 나가고,
결국 문제를 더이상 쪼갤 수 없는 arrSum([]) 까지 함수가 호출되는 것을 볼 수 있다.
arrSum([]) 는
조건문에 의해 더이상 자기자신을 호출하지 않고, 숫자 0을 리턴하면서 종료.
그 결과 중첩되어있던 함수들도 연쇄적으로 숫자를 리턴하고,
최종적으로는 배열의 모든 요소의 합을 리턴하면서 문제가 해결된다.팩토리얼
- 팩토리얼이란 자기 자신부터 시작해서 1 감소한 숫자들을 곱한 값 or 주어진 수 부터 1까지 차례로 곱하기
4! = 4 x 3 x 2 x 1 =24
function factorial(x) {
if (x < 0) return;
// base case
if (x === 0) return 1;
// recursion case
return x * factorial(x - 1);
}
factorial(3);
// 6- 값3인 함수를 호출.
factorial(3);2.함수 실행 , if문을 넘어가고 재귀 부분을 실행. 3과 factorial(3-1)이 곱해진 결과를 리턴.
return 3 * factorial(2);3.factorial(2) 실행, 다시 if문 넘어가고 재귀 부분 실행.2와 factorial(2-1)이 곱해진 결과를 리턴.
return 2 * factorial(1);4.factorial(1) 실행, if문이 또 한번 넘어가게 되고 재귀 실행. 1과 factorial(1-1)이 곱해진 결과를 리턴.
return 1 * factorial(0);factorial(0) 실행, 0은 base case. 그래서1을 리턴.
if(x === 0) return 1;factorial(3) returns 3 * factorial(2)
factorial(2) returns 2 * factorial(1)
factorial(1) returns 1 * factorial(0)
factorial(0) returns 1
//마지막리턴
//재귀 함수는 안에서 부터 바깥으로 값을 반환해 나간다.
factorial(0) returns 1 => 1
factorial(1) returns 1 * factorial(0) => 1 * 1
factorial(2) returns 2 * factorial(1) => 2 * 1 * 1
factorial(3) returns 3 * factorial(2) => 3 * 2 * 1 * 1
// 3 * 2 * 1 * 1 = 6 마지막 리턴을 끝으로 모든게 풀린다.
모든 중첩된 함수 중 가장 안쪽에 중첩된 함수가 먼저 리턴된다.
문자열뒤집기
function revStr(str) {
if (str === '') return '';
return revStr(str.substr(1)) + str[0];
}
revStr('cat')
// tacstr === ""는 base case. 문자열 없음, 빈값.
return rev(str.substr(1)) + str[0]; 재귀 부분.
문자열은 음수를 가질 수 없다. 그래서 함수에 문자열만 입력하면된다.
- cat 문자열 함수를 호출
revStr('cat');2.재귀 실행
자바스크립트에서,
substr()메소드는 특정한 위치에서 시작하는 문자열을 리턴.
->cat.substr(1) === 'at'
str[0]는 문자열에서 첫 인덱스에 위치한 문자를 내보낸다.
->cat[0] === 'c'
return revStr(str.substr(1)) + str[0];
// 동일한 결과
return revStr('at') + 'c';return revStr(str.substr(1)) + str[0];
// 동일한 결과
return revStr('t') + 'a';가장 작은단위 쪼개기
return revStr(str.substr(1)) + str[0];
// 동일한 결과
return revStr('') + 't';
base case 실행,빈 문자열 리턴.
if(str === '') return '';이제 함수가 결과를 반환합니다. 모든 것이 풀렸고 순서대로 반환합니다.
return '' + 't' + 'a' + 'c';
// tac정리
revStr('cat') returns revStr('at') + 'c'
revStr('at') returns revStr('t') + 'a'
revStr('t') returns revStr('') + 't'
revStr('') returns ''
모든 중첩된 합수를 풀어헤쳐?놨고,
모든 중첩된 함수의 가장 안쪽 부터 먼저 반환. 순서대로 반환 하며, 쌓인 재귀가 풀린다.
revStr('') returns '' => ''
revStr('t') returns revStr('') + 't' => '' + 't'
revStr('at') returns revStr('t') + 'a' => '' + 't' + 'a'
revStr('cat') returns revStr('at') + 'c' => '' + 't' + 'a' + 'c'
// tac
정리
재귀함수의 입력값과 출력값을 정의하여
최대한 문제를 쪼갠후 base case에 따라 단순한 부분부터 해결. 중첩부분에 가장안쪽부터 해결.
function arrSum(arr) {
// base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
if (arr의 길이가 0인 경우) {
return 0;
}
// recursive case : 그렇지 않은 경우
return 요소1 + arrSum([요소2, ... , 요소n]);
}
// 일반적인 재귀 함수의 템플릿
function recursive(input1, input2, ...) {
// base case : 문제를 더 이상 쪼갤 수 없는 경우
if (문제를 더 이상 쪼갤 수 없을 경우) {
return 단순한 문제의 해답;
}
// recursive case : 그렇지 않은 경우
return 더 작은 문제로 새롭게 정의된 문제
}