정의

내가 나를 반복하는 함수이자 반복문과 호환이 됩니다. 즉 반복문이면 재귀함수가 되고 재귀가 되면 반복문이 가능합니다

반복문의 경우

1에서 100까지의 수를 더 하는 경우

let s= 0;
for(var i= 1; i<101;i++){
		s+=i;
}
console.log(s) //5050

그런데 이러한 경우에는 100번 순회를 하지만, 누적합의 경우 별개의 공식이 존재합니다.

$n(n+1)/2$

위의 공식을 이용해 주면됩니다. 반복문의 경우에는 **O(n)**으로 n이 커지면 커질수록 반복 횟수가 늘어나는 n의 비례함을 이야기하는 것이고 , 수학 공식의 경우에는 **O(1)**이 됩니다. 한번만 하면 된다는 것이지요.

재귀의 경우

재귀함수에서의 1에서 100까지의 합을 확인해볼까요?

function f(n){
	if (n<=1){
			return 1

			}return n+f(n-1)

}
console.log(f(100))//5050

이 경우에도 for문을 이용 한 것과 동일하게 5050이 나오는 것을 확인할 수 있습니다. 위의 재귀함수를 표로 표현한다면 아래와같은 모습이 나올 것 입니다.

위의 코드는 결국 곱에서도 동일하게 적용됩니다

function f(n){
	if (n<=1){
			return 1

			}return n*f(n-1)

}
console.log(f(100))

재귀함수 사례

재귀함수 2진수 변환

반복문의 경우

let result = "";
let x=11;

while (true) {
  if (x % 2 == 0) {
    result += "0";
  } else {
    result += "1";
  }
  x = Math.floor(x / 2);

  if (x == 1 || x == 0) {
    result += String(x);
		break;
  }
}
console.log(result.split('').reverse().join(""));

재귀함수의 경우