이번 게시물에서는 재귀(Recursion)에 대해서 다뤄보도록 하겠당!_! 먼저 재귀 함수를 사용하는 이유에 대해서 살펴보고, 재귀가 어떻게 진행되는지 스택호출 순서에 대해서 살펴볼 것이당. 그리고 순서대로 재귀함수 기본, 반복문과 재귀함수를 이용한 팩토리얼, Helper 메소드 재귀까지 살펴보쟝!_! 쉬운 코드들로 진행을 하니 이해하기는 편할 것이당!_! 레츠꼬우꼬우!!
재귀는 자기자신을 호출하는 절차. 자바스크립트(JavaScript)나 코드를 가지고 하는 모든 일. 우리가 말하는 재귀는 자기자신을 호출하는 함수. 스스로를 호출. Laugh라는 이름의 함수가 존재하면 내부 함수의 이름도 Laugh.
▷ 살펴보기 (재귀 예시)
두 가지의 서로 다른 메소드에 걸쳐 실행되기는 하지만, 결국에는 이 사이클에서 두 함수가 서로를 호출. 즉, readValue가 readObject를 호출하고, readObject는 readValue를 호출하고, readValue는 다시 readObject를 호출. 이 사이클이 계속해서 반복.
DOM은 모든 요소가 중첩된 트리 구조. 그래서 div 안의 div에 div가 들어 있는 중첩 계층이 100개나 될 수도 있음. 만약에 그 모든 걸 살펴보고자 한다면, 흔한 접근법 중 하나는 재귀적으로 작동하는 코드를 작성.
🐣 스택 호출하기
▷ 개념
거의 모든 프로그래밍 언어에는 함수 호출을 관리하는 데이터 구조가 있음. 호출된 함수는 종종 다른 함수가 반환될 때까지 기다림. 특별한 순서가 있으며, 함수들은 무작위로 실행되지 않음. 먼저 호출되는 함수가 있고, 그 함수 내에서 두 번째 함수가 호출. 함수들은 올바른 순서대로 실행되어야 하고 이를 처리하는 데이터 구조가 있음. JavaScript의 경우, 호출 스택.
호출 스택을 종이 더미로 생각할 수 있지만, 스택이라는 데이터 구조. 함수를 호출할 때, 그 함수는 호출 스택의 맨 위에 쌓이는데, 마치 책상 위에 종이 더미를 쌓는 것처럼, 새로 추가된 함수는 맨 위에 위치함. JavaScript는 return 키워드를 찾거나 함수 내에서 더 이상 실행할 코드가 없을 때, 컴파일러가 스택의 맨 위 항목을 제거. 스택의 개념을 설명할 때, 그것을 책상 위의 종이 더미에 비유하게 되는데, 무언가를 위에 놓기. 심지어 무언가를 꺼낼 때도, 위에서부터 꺼냄.
- 개발자도구 sources > 버튼 or command + enter 실행으로 콜스택 확인 (next step 눌러보면서 순서 확인) - 재귀 함수에서 호출 스택 많이 사용 - 보통의 경우 함수 완료 > 호출 스택 아래 > 제거 - 재귀의 경우 계속해서 새로운 함수 호출 스택에 추가(동일 함수 계속 추가, 추가된 함수는 호출 기다림) - 어느 지점에 호출 종료 필요(종료 지점 없으면 무한 루프빠짐)
호출 스택은 자바스크립트의 보이지 않는 곳에서 작동하는 정적 데이터 구조(static data structure). 그 의미는 항목이 꼭대기에 추가되고 마찬가지로 꼭대기에서부터 제거되며, 함수가 호출되면 이 구조에 추가된다는 것.
🌼 첫번째 재귀함수
▷ 기본 요소
라인을 끝내는 종료 조건 : 종료 지점이 있어야만 무한루프에 빠지지 않음
다른 입력 값 : 계속해서 같은 값을 호출하는 것이 아니라 매번 다른 데이터로 함수 호출
▷ 코드로 살펴보기
countdown.js
// Recursive Version
function countDown(num) {
if (num <= 0) {
console.log("All done!");
return;
}
console.log(num);
num--;
countDown(num);
}
countDown(3)
// Iterative Version 재귀 사용하지 않고 반복문 사용
function countDown(num) {
for (var i = num; i > 0; i--) {
console.log(i);
}
console.log("All done!")
}
🌼 퀴즈
자바스크립트는 함수 호출하기 위해 어떤 도구 사용?
스택 호출
기본 케이스는 무엇?
재귀가 끝난 상태
🌼 두 번째 재귀함수
▷ 코드로 살펴보기
sumrange.js
function sumRange(num) {
if (num === 1) return 1;
return num + sumRange(num - 1);
}
sumRange(4)
위의 순서로 진행이 되고 다시 살펴보면 거꾸로 진행됨 스택과정, 넣고 위에있는것부터 다시 계산하여 뺌
sumRange(3) // 아래에서 위로 순서대로 하여 6 나옴.
return 3 + 3 // sumRange(2) 반환값 3 +3 = 6 ------ (3)
return 2 + 1 // sumRange(1) 반환값 1 + 2 = 3 ------ (2)
return 1 //함수 종료 1 ------ (1)
🐣 반복문으로 팩토리얼 구현하기
▷ 코드로 살펴보기
factorial_iterative.js
function factorial(num){
let total = 1;
for(let i = num; i > 1; i--){
total *= i
}
return total;
}
반복문으로 팩토리얼 구현(비재귀적 해결법)
factorial(4) 할 경우 4 * 3 * 2 순서로 i값 작아지면서 진행하여 24 결과 도출
마지막 1의 경우 그전 값의 * 1이기 때문에 i값 1보다 큰 값까지만 진행
🐣 재귀 호출로 팩토리얼 구현하기
▷ 코드로 살펴보기
factorial_recursive.js
function factorial(num){
if(num === 1) return 1;
return num * factorial(num-1);
}
재귀적 해결법
num 이 1과 같을 때 종료 (반복문의 경우 i가 1보다 큰 값까지만 진행)
그 전까지는 계속해서 factorial 재귀적 호출
factorial(4)로 num이 4로 들어오면
factorial(4) 진행할 경우, 4 * factorial(3) 3 * factorial(2) 2 * factorial(1) 순으로 되고, 계산은 factorial(1) = return 1되어서 종료되면서 2 * 1(factorial(1)값) = 2 3 * 2(factorial(2)값) = 6 4 * 6(factorial(3)값) = 24 순으로 진행
🐣 helper_method_재귀
▷ 설명
이전까지 살펴본 재귀 함수들은 단일 단독 함수(스스로를 재귀)
헬퍼 메소드 재귀의 경우 코드가 실제로 뭘 하지는 않음
두 개의 함수 존재
외부 함수와 내부에는 재귀 함수
아래의 재귀함수 또한 자기 자신 호출
헬퍼 메소드 재귀는 그냥 재귀적이지 않은 외부 함수가 재귀적인 내부 함수(inner function)를 호출하는 패턴
function outer(input){
var outerScopedVariable = []
function helper(helperInput){
// modify the outerScopedVariable
helper(helperInput--)
}
helper(input)
return outerScopedVariable;
}
메인 외부 함수는 우리가 외부에서 호출
외부 함수를 호출해서 무언가를 내부로 전달 가능
외부 함수 안에 또 다른 함수, 재귀적으로 자기 자신 호출
배열이나 데이터 목록 같은 걸 컴파일(compile)해야 할 때 흔히 이렇게 작업
타뷸레이션(tabulation)을 하는 게 아님. 팩토리얼이나 다른 함수를 사용했을 때처럼 하나의 값을 계속해서 곱하는 것도 아니고, 범위의 합계를 내는 것도 아님.
helper_method_recursion.js
어느 배열에서 모든 홀수값을 수집하는 것과 같은 같은 작업을 수행 중이라면, 헬퍼 메소드 재귀를 사용하는 게 편함
빈 배열을 생성하고 그 안에 모든 데이터를 입력. 그러고 나서 헬퍼 함수를 호출.
function collectOddValues(arr) {
let result = [];
function helper(helperInput) {
if (helperInput.length === 0) {
return;
}
if (helperInput[0] % 2 !== 0) {
result.push(helperInput[0])
}
helper(helperInput.slice(1))
}
helper(arr)
return result;
}
collectOddValues([1, 2, 3, 4, 5, 6, 7, 8, 9])
위에서 재귀 논리는 result를 조작할 것. result에 값 추가
이렇게 작업하는 이유는 result를 collectOddValues(외부)에 정리하면 함수가 재귀로 호출될 때마다 빈 배열로 리셋되기 때문에
헬퍼 메소드 재귀를 통해서 해당 문제 해결 result 값은 helper 재귀 속에서
실제 논리는 helper이고, 배열을 사용해서 helper(arr)에서 실행
종료 조건은 helperInput.length가 0일 때,
그 외에는 홀수를 걸러냄. result 값에 push
짝수 일 경우 helper 배열 slice한 부분배열로 다시 helper 재귀호출
🐣 순수_재귀
collect_odds_pure_recursion.js
▷ 설명
재귀가 아닌 반복을 사용해서 홀수 반환 문제 해결(쉬움)
헬퍼 재귀를 사용할 수도 있지만 다음과 같이 순수 재귀 사용해서 작업 수행 가능
외부 데이터 구조 사용하지 않음
코드는 더 짧지만 이해하는데 어려울 수 잇음
function collectOddValues(arr) {
let newArr = [];
if (arr.length === 0) {
return newArr;
}
if (arr[0] % 2 !== 0) {
newArr.push(arr[0]);
}
newArr = newArr.concat(collectOddValues(arr.slice(1)));
return newArr;
}
collectOddValues([1, 2, 3, 4, 5])
함수가 호출될 때마다 newArr 배열 초기화
리셋되어도 상관없음. 실제 작업은 계산이 완료 됐을 때 모든 배열을 하나로 합쳐서 반환하는 것
