<230209 자료구조> 알고리즘과 재귀함수

알고리즘

• 자료구조를 이용하여 어떠한 문제를 해결하는 구체적인 방식
• 컴퓨터가 따라 할 수 있도록 문제를 해결하는 절차나 방법을 자세히 설명하는 과정
• 문제 상황이 주어졌을 때 제한된 시간과 메모리 내에서 가장 효율적으로 문제를 해결할 수 있는 방법.

재귀 함수

• 정의 : 함수 안에서 자기 자신을 다시 호출하는 것. (마치 거울 속에 있는 거울을 보는 느낌)
• 장점
  • 이해하기 쉽다.
  • 프로그램의 오류가 생기는 가능성이 줄어든다.
  • 프로그래임이 정상적으로 돌아가는지에 대한 증명이 쉬어진다.
  • 변수 사용을 줄여 준다.
  • 알고리즘 자체가 재귀적인 표현이 자연스러운 경우(+가독성 향상)
• 단점
  • 반복문보다 메모리 사용량 많고 수행 시간이 더 길어질 수 있다.
  • 무한 반복이 일어나는 경우 스택 오버플로우 에러가 발생한다.

재귀 패턴을 다룰 때 주의할 점

• 종료조건이 없거나 잘못됐을 때
• 잘못된 값을 리턴하거나, 리턴을 해주지 않았을 때

const factorial = num => {
  if (num === 1) return 1; // 종료조건에 도달할 수 없음
  return num * factorial(num); // 
};

const factorial = num => {
  if (num === 1) console.log(1); // 종료조건이 잘못됐기 때문(return이 없다)
  return num * factorial(num - 1); // 
};

콜 스택이 꽉 차서 터져버리는 것(Maximum call stack size exceeded) 즉, 스택 오버플로우(stack overflow)가 일어날 수 있다.

하향식, 상향식 접근법 (의사결정구조와도 비슷)

하향식 분석 - top - bottom

• 출력 형태를 만들어 놓고 회수하는 형태
• 큰 문제를 푸는데 작은 문제를 활용하는 형태
• 결과가 이전의 결과에 영향을 받는 것(꼬리 재귀함)

상향식 분석 - bottom - up

• 가장 아래쪽부터 위로 쌓아 올리면서 분석하는 방법
• 일반 재귀 함수
• 하향식 분석과 분석 방식이 정반대
  • f(n+1) = f(n) + a

재귀 사용 예시

• JSON(parse)등 또한 오브젝트(object)를 순회할 때 재귀를 사용
• 웹에서 DOM 등을 순회할 때도 사용. DOM API querySelector 등
• 내부적으로 메서드를 사용하기도 함
• 알고리즘, 코딩 테스트 등에도 사용
  
  
  

재귀 함수 예시

// 코드를 실행하면 하향식 방식으로 1까지 내려갔다가 다시 올라옴
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));

꿀팁

1. 코딩테스트 문제를 풀 때 제약조건을 잘 읽어볼 것
2. 재귀를 구현할 때 내가 미리 알고있거나 유추되는 범위를 기저조건으로 걸 것
3. 하향식 구조는 윗 사람들이 만들어 놓은 틀대로 수행해나가는 것(큰 조직 등)
4. 상향식 구조는 아랫 사람들끼리 이런 기능을 만들고 싶다하여 아래부터 위까지 쌓아올리는 방식(작은 조직, 토스 등)
5. 지금이 아니라 먼 나중에 멀티스레디드 자바스크립트 책이라는 것도 읽어보면 좋을 듯
6. nested navigation (네비 안에 네비 재귀) 현업에서 매우 많이 쓰임
7. 컴포지트 패턴도 중요함
8. 하향식으로 접근하면 좋은 재귀와 상향식으로 접근하면 좋은 재귀 검색해보면 좋을 듯