재귀함수

함수 안에 자신의 함수를 다시 호출하는 함수를 의미합니다.

JSON.parse, JSON.stringify 등등도 재귀함수로 작성했습니다.
재귀 함수에서 생각할 것은 항상 종료 조건이 있어야 합니다.
종료 조건이 없거나 반환 값이 없는 경우 StackOverflow 가 발생할 수가 있습니다.

정말 기초적인 재귀 함수

function countDown(num) {
    if(num <= 0) return console.log('완료')

    console.log(num)
    num--
    return countDown(num)
}

두번째 재귀 함수

function sum(num) {
    if(num === 1) return 1
    return num + sum(num - 1)
}

재귀 펙토리얼

function factorial(num) {
    if(num === 1) return 1
    return num * factorial(num-1);
}

순수 재귀 vs Helper 메서드 재귀

순수 재귀

함수 내에서 자기 자신을 직접적으로 호출합니다.
함수가 별도의 외부 헬퍼 함수를 사용하지 않고 자체적으로 재귀적으로 동작합니다.
예제로 팩토리얼을 계산하는 함수를 순수 재귀로 구현하면 다음과 같습니다:

function factorial(num) {
    if (num === 0 || num === 1) {
        return 1;
    } else {
        return num * factorial(num - 1);
    }
}

헬퍼 메서드 재귀

외부에서 헬퍼(helper) 함수를 정의하고, 이 헬퍼 함수가 실제 재귀 호출을 담당합니다.
메인 함수는 초기 설정을 하고, 헬퍼 함수를 호출하여 재귀적으로 동작합니다.
예를 들어, 배열의 합을 구하는 함수를 헬퍼 메서드 재귀로 구현하면 다음과 같습니다:

function arraySum(arr) {
    function sumHelper(index) {
        if (index === arr.length - 1) {
            return arr[index];
        } else {
            return arr[index] + sumHelper(index + 1);
        }
    }
    return sumHelper(0);
}

순수 재귀는 간단하며 깔끔한 코드를 가질 수 있지만, 매번 재귀 호출할 때마다 새로운 함수 호출 스택이
생성되므로 스택 오버플로우의 가능성이 있습니다. 반면에 헬퍼 메서드 재귀는 외부 함수 호출 스택을
공유하므로 스택 오버플로우에 대한 위험이 적습니다.
선택은 상황에 따라 다르며, 어떤 방식이 코드를 더 이해하기 쉽게 만들고 성능 측면에서
더 효율적인지에 따라 결정될 수 있습니다.

reverse 함수를 재귀함수로 직접 구현하기

function myReverse(str){
	if(str.length <= 1) return str;
  	return myReverse(str.slice(1)) + str[0]
}

피보나치 수열 구하기

function fib(num){
	if(num <= 2) return 1
  	return fib(num-1) + fib(num-2);
}

재귀함수로 직접 Math.pow() 만들기

function myPow(num, exponent){
	if(exponent === 0) return 1;
  	return num * myPow(num, exponent - 1);
}