알고리즘
- 자료구조를 이용하여 어떠한 문제를 해결하는 구체적인 방식
- 컴퓨터가 따라 할 수 있도록 문제를 해결하는 절차나 방법을 자세히 설명하는 과정
- 문제 상황이 주어졌을 때 제한된 시간과 메모리 내에서 가장 효율적으로 문제를 해결할 수 있는 방법.
재귀 함수
- 정의 : 함수 안에서 자기 자신을 다시 호출하는 것. (마치 거울 속에 있는 거울을 보는 느낌)
- 장점
- 이해하기 쉽다.
- 프로그램의 오류가 생기는 가능성이 줄어든다.
- 프로그래임이 정상적으로 돌아가는지에 대한 증명이 쉬어진다.
- 변수 사용을 줄여 준다.
- 알고리즘 자체가 재귀적인 표현이 자연스러운 경우(+가독성 향상)
- 단점
- 반복문보다 메모리 사용량 많고 수행 시간이 더 길어질 수 있다.
- 무한 반복이 일어나는 경우 스택 오버플로우 에러가 발생한다.
재귀 패턴을 다룰 때 주의할 점
- 종료조건이 없거나 잘못됐을 때
- 잘못된 값을 리턴하거나, 리턴을 해주지 않았을 때
const factorial = num => {
if (num === 1) return 1;
return num * factorial(num);
};
const factorial = num => {
if (num === 1) console.log(1);
return num * factorial(num - 1);
};
콜 스택이 꽉 차서 터져버리는 것(Maximum call stack size exceeded) 즉, 스택 오버플로우(stack overflow)가 일어날 수 있다.
하향식, 상향식 접근법 (의사결정구조와도 비슷)
하향식 분석 - top - bottom
- 출력 형태를 만들어 놓고 회수하는 형태
- 큰 문제를 푸는데 작은 문제를 활용하는 형태
- 결과가 이전의 결과에 영향을 받는 것(꼬리 재귀함)
상향식 분석 - bottom - up
- 가장 아래쪽부터 위로 쌓아 올리면서 분석하는 방법
- 일반 재귀 함수
- 하향식 분석과 분석 방식이 정반대
재귀 사용 예시
- JSON(parse)등 또한 오브젝트(object)를 순회할 때 재귀를 사용
- 웹에서 DOM 등을 순회할 때도 사용. DOM API querySelector 등
- 내부적으로 메서드를 사용하기도 함
- 알고리즘, 코딩 테스트 등에도 사용
재귀 함수 예시
function recurFactorial(number){
if(numer == 1) return number;
const res = number * recurFactorial (number -1)
console.log('끝!!')
return res;
}
console.log(factorial(5));
!! 재귀를 구현할 때 내가 미리 알고있거나 유추되는 범위를 기저조건으로 걸면 더 좋은 조건의 재귀함수를 만들 수 있다.
꼬리 재귀
- 재귀 함수를 호출하고 종료가 되는 마지막 함수에 도달했을 때 최종 값만 반환하는 형태
- 중간에는 더 이상 연산을 수행할 필요가 없으므로, 굳이 돌아갈 스택을 기억하지 않고 있어도 된다.
컴파일러가 꼬리 재귀 최적화를 지원하고 있다면 성능이 개선되지만, 지원하고 있지 않다면 일반 재귀 함수로 구현했을 떄와 차이가 없다.
function factorial2(n, total = 1) {
if (n === 1) {
return total;
}
return factorial2(n - 1, total * n);
}
log(factorial2(5));
꿀팁
- 코딩테스트 문제를 풀 때 제약조건을 잘 읽어볼 것
- 재귀를 구현할 때 내가 미리 알고있거나 유추되는 범위를 기저조건으로 걸 것
- 하향식 구조는 윗 사람들이 만들어 놓은 틀대로 수행해나가는 것(큰 조직 등)
- 상향식 구조는 아랫 사람들끼리 이런 기능을 만들고 싶다하여 아래부터 위까지 쌓아올리는 방식(작은 조직, 토스 등)
- 지금이 아니라 먼 나중에 멀티스레디드 자바스크립트 책이라는 것도 읽어보면 좋을 듯
- nested navigation (네비 안에 네비 재귀) 현업에서 매우 많이 쓰임
- 컴포지트 패턴도 중요함
- 하향식으로 접근하면 좋은 재귀와 상향식으로 접근하면 좋은 재귀 검색해보면 좋을 듯