재귀함수

재귀함수

함수 내부에서 '자기 자신을 호출'하는 함수
무한루프에 빠지지 않게 종료 조건 설정 필수!

재귀함수의 장점
1. 원하는 결과를 도출하는데 있어 가독성을 높일 수 있음
2. 일부 알고리즘에서 반복문보다 재귀 함수가 더 직관적임

재귀함수 단점
1. 함수 호출 때마다 스택이 쌓이는데 스택이 너무 깊어질 경우 스택 오버플로우 발생할 수 있음

💡스택 오버플로우💡

사실상 컴퓨터의 메모리에는 한계가 있다. 
그러므로 무한 루프에 빠지게 되면 
스택 오버플로우 문제가 발생 하게 된다. 

자바에서 해당 코드를 수행하면 콘솔창에 뜨는
StackOverflowError 을 확인할 수 있을 것이다. 

---

대표 예제 == 팩토리얼

• 팩토리얼
  : 자연수 n에 대해서 1부터 n까지의 모든 자연수를 곱한 값을 의미합니다.

int factorial(int n) { 
    if (n === 1) { 
        return 1; 
    } 
    return n * factorial(n-1);
}

factorial(5) = 5 * factorial(4)
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 * factorial(0)
factorial(0) = 1

위와 같이 함수가 진행되면서 콜스택이 쌓이게 된다.
factorial(5)는 반환값을 기다리고 factorial(4)도 호출되고 반환값을 기다리게 된다. 그리고 n==1이 될때 값을 출력할 수 있게 된다.

하지만 n==1일때라는 조건이 사라지면 무한루프에 빠지게 되면서 앞서 말했던 stack overflow가 발생하게된다.

---

참고 블로그
참고 블로그