재귀 함수

ROCKBELL·2022년 12월 16일
0

자바스크립트

목록 보기
15/25

재귀함수

재귀 함수는 자기 자신을 호출하는 함수를 말하며,
간단한 동작 하나를 반복적으로 처리해야 할 때,

  • 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
  • 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우
  • 코드를 더욱 간결하고 이해하기 쉽게 작성하려는 경우

를 만족한다면 재귀 함수를 사용 할 수 있다

재귀적 사고

  • 입력값과 출력값 정의
  • 문제를 쪼개고 경우의 수 나누기
    • 더이상 쪼갤 수 없는 경우
    • 그렇지 않은 경우
  • 단순한 문제부터 해결
    • 재귀의 탈출 조건 구성 -> base case
  • 복잡한 문제 해결
    • 문제를 쪼개서 더 작은 문제로 새롭게 정의하여 재귀적 구현을 통해 해결 -> recursive case

재귀함수와 메모리 사용량

재귀의 깊이는 스택에 들어가는 실행 컨텍스트 수의 최댓값가 같다
재귀의 깊이와 비례한 메모리를 차지하기 때문에 메모리 요구사항에 주의해야 한다

함수가 호출될때마다 입력값, 결과값, 리턴 후 돌아갈 위치등이 스택(Stack)이라는 데이터 저장공간에 보관된다

재귀를 사용하는 이유는 가독성이 좋아 코드 이해도가 높아지고 유지보수에 이점이 있기때문이며, 메모리 최적화를 신경써지 않아도 되는 경우에는 재귀를 사용해도 괜찮다

다만, 무리하게 함수호출을 하면 스택 공간이 꽉차버리는 스택 오버플로우 현상이 발생할 수 있는 엄청난 위험성이 있다는 것도 염두해야한다

꼬리 재귀

이러한 재귀함수의 위험성을 방지하기위해 보완하는 방법중 하나가 꼬리재귀 이다

  • 일반 재귀
function factorial(n) {
  if(n === 1){
  	return 1;
  }
  return n * factorial(n - 1);
}
  • 꼬리 재귀
function factorial(n, total = 1) {
	if(n === 1){
    	return total;
    }
  return factorial(n - 1, n * total)
}

이 방식을 사용하면 호출이 끝났을때, 이전 함수의 상태(돌아갈 위치)를 유지하지 않고, 추가 연산도 하지 않고 결과만 바로 반환하여 스택이 넘쳐나는 문제를 해결 할 수 있게 된다

profile
luv it

0개의 댓글