재귀함수란?

-재귀함수란 자기 자신을 호출하는 함수를 말한다. 종료 조건이 충족될 때까지 반복적으로 스스로를 불러내면서 주어진 작업을 수행하는 것이다. 

재귀함수는 호출될 때마다 메모리의 스택에 쌓이게 된다. 한계치 이상으로 호출돼서 스택이 넘처버리면 메모리 부족으로 에러가 발생하게 된다. 

속도 면에 있어서도 재귀함수는 jump가 잦아서 반복문에 비해 시간을 더 소모한다. 
이런 문제를 해결하기 위해 많은 언어들에서 꼬리 재귀 최적화 (Tail Call Optimization) 라는 기능을 제공한다. 

재귀함수를 컴퓨터가 재해석해서 선형 알고리즘으로 만들어 실행한느 것이다. 

그럼 아무리 반복이 많아도 스택이 넘치는 일은 일어나지 않는다. 

재귀함수가 꼬리 재귀가 되려면 return하는 값이 함수 그 자체만 호출하는 형태이여야 한다.    ex) canTailRecurse(arg)

다른 것(들)이 섞여 return: 꼬리재귀 불가   ex) n * canTailRecurse(arg)

 

---

 

하노이의 탑을 재귀함수로 수행하는 코드

function hanoi(num, from, to, other) {
	if(num == 0) return;
	hanoi(num - 1, from, other, to);
	console.log(${from}번에서 ${to}로 옮긴다.);
	hanoi(num - 1, other, to, from);
}

 

인자로는 출발지와 목적지, 그리고 나머지 기둥의 번호를 받는다. 
스스로를 호출하는 코드가 두 번있고, 그 사이에 원반을 어디에서 어디로 한 번 옮길지를 출력

첫 번째 호출에서는 받아온 원반 개수보다 하나 적은 원반들을 목적지가 아닌 곳으로 재귀적으로 이동시킨다. 그 다음에는 맨 아래 원반을 목적지로 이동시키고 마지막으로, 다른 곳으로 옮겼던 원반들을 그 위에 얹는 것