0828 주말 자습

냐하호후·2021년 8월 28일

TIL

목록 보기

33/101

재귀함수와 메모리 사용량 간의 관계

재귀함수는 함수의 호출이 반복적으로 이루어지기 때문에 성능에 좋지 않다고 한다.
자칫 스텍 오버플로우를 일으킬 수 있다.
그렇다면 우리는 왜 재귀함수를 사용할까?

알고리즘 자체가 재귀적으로 표현하는게 가독성이 좋을 때
변수 사용량을 줄일 수 있다.
여기서 변수 사용량을 줄인다는 말은 말 그대로 메모리에 잡히는 변수를 줄여준다는 뜻이 아니다. mutable state(변경가능 상태)를 제거해서 오류 발생 확률을 낮출 수 있다는 뜻이다.

꼬리 재귀 (tail recursion)

꼬리 재귀란, 재귀 호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않는 재귀의 형태이다.
일반적인 재귀함수

function fac(n){
  if(n === 1){
    return n;
  }
  return n*fac(n-1);

꼬리재귀

function fac(n){
  if(n === 1){
    return n;
  }
  let result = fac(n-1);
  return n*result;

단순하게 본다면 두 코드의 차이도 없고 결과 또한 똑같이 나올 것이다. 하지만 스텍창을 확인하면 일반적인 재귀함수는 스텍이 계속 쌓이게되고 꼬리재귀는 한번만 호출 될 것이다. 단순하게 말해서 일반적인 재귀함수는 리턴 값이 함수이기 때문에 계속 해서 함수를 호출한다.
하지만 꼬리재귀의 경우는 함수를 호출하고 그 함수를 변수에 할당하고 사용한다. 이 처럼 더 이상 함수에서 추가 연산이 일어나지 않는다. 이 처럼 스텍이 계속 쌓이는 재귀의 단점을 보완한 것이 꼬리함수 이다.

하노이의 탑 재귀 (tower of hanoi in recursion)

하노이의탑 참고 링크

하노이의 탑 참고 링크2

function hanoi(num,from,to,other){ //원반갯수,출발지 기둥번호 , 목적지 기둥 번호, 나머지 기둥번호
  if (num === 0 ) return ;
  hanoi(num -1 , from, other , to);
  //받아온 원반 갯수보다 하나 작은 원반들을 목적지가 아닌 곳으로 재귀적으로 옮긴다.
  hanoi(num-1, other , to ,from);
  //맨 아래 원반을 목적지로 이동시키고 다른곳으로 옮겼던 원반들을 그 위에 얹는다.
}