[자바스크립트] 재귀함수

재귀함수 recursion function

함수 내에서 자기 자신을 다시 호출하는 함수

함수의 복사본을 만들어서 복사본을 실행함 -> 재귀함수에는 재귀 탈출조건을 작성해야 함  (e.g. 팩토리얼, 피보나치)

재귀함수(top-down)의 특성상, 반복문(bottom-up)으로 구할 때보다 성능상 불리, 코드의 가독성은 좋음

자바스크립트 엔진은 최대 재귀 깊이를 제한(10,000 개정도)하고, 엔진에 따라서 더 많은 깊이를 허용할 수 있음 

 

▷ 재귀 함수 구현 방법 

1) for 루프 

2) 작업 단순화 후, 자기 자신 호출

3) 삼항 연산자 사용 

      // n까지 더하기 
        function funcSum(n){
            if(n>0){
                //값을 더해줘야 함 
                // n=0일 때, return 0
                // n=1일때, return f(n-1) +n = 0 +1 // return 1 
                // n=2, return f(n-1) +n =  return 1 + 2 // return 3
                // n=3, return f(n-1) +n = f(2) = return 3 +3 // return 6
                // 그래서 최종 리턴값은 6 
                return funcSum(n-1) +n;
            }else {
                // 값을 리턴
                return 0;
            }
        }

        document.write(funcSum(3));

// 재귀함수 - 자기자신을 부르는
// 처음 함수의 호출 결과가 나오면(재귀가 끝나면) 다음 함수로 넘어가는 호출 순서를 가짐

        function funcFor(n){
            if(n>0){
                // n이 0보다 클 때 자기 자신 반복
                // n이 무한반복되지 않도록 1씩 줄임
                funcFor(n-1)
            }else{
                // n이 0일때 종료
                return 0;
            }
            document.write(`<p>반복합니다</p>`);
        }
        
 	funcFor(3) // 함수 실행

재귀적 함수 호출 과정 (출처.https://atoz91.tistory.com/54)

---

재귀의 활용

1) 피보나치 수열 

재귀적 형태를 띄는 대표적인 수열로, 앞 두개를 더해 현재의 수를 만들어가는 수열

init Fibo(int n) {
	if(n == 1)
    	return  0;
    else if(n == 2)
    	return 1;
    else
    	return Fibo(n-1) + Fibo(n-2);
   }

 

2) 팩토리얼 

주어진 수보다 작거나 같은 모든 양의 정수의 곱

const factorial = (n) => {
	if(n === 0) {
    	return 1;
        } else {
        	return n * factorial(n-1);
        }
    }
 };
 factorial(4);

---

참고. 스택(Stack)

컴퓨터는 호출 스택이라 불리는 스택을 사용해 함수를 실행 

일반적인 프로그래밍에서도 중요하나 재귀를 사용할 때 더 중요함

자료를 넣고(push) 빼는 것(pop)의 자료구조를 Stack이라고 함

자료의 입출력이 한쪽 끝에서만 일어나기 때문에, 선형 구조이며 LIFO(Last In first Out) 후입선출 방식 

 

참고자료 

1) 팩토리얼 및 피보나치 예시 : https://velog.io/@leehaeun0/%ED%95%A8%EC%88%98%EC%9D%98-%EC%9E%AC%EA%B7%80%EC%A0%81-%ED%98%B8%EC%B6%9C%EC%9D%98-%EC%9D%B4%ED%95%B4

2) 재귀에 대해 쉽게 알아보자 : https://codechasseur.tistory.com/30