재귀함수(Recursion)

 

재귀함수(Recursion)

---

Stack 개념을 이용해 자기 자신을 다시 호출하며 반복하는 함수이다.

구성

• 탈출 조건, 연산, 재귀 호출로 이루어진다.
• 탈출 조건을 잘못 설정하면 Stack Overflow가 발생한다.

public static int rSum(int n){
    // 탈출 조건
    if(n == 0)
        return 0;
    // 재귀 호출
    return n += rSum(n-1);
}

장점

• 가독성을 높일 수 있다.(재귀적인 표현이 자연스러운 경우)

단점

• 호출이 많아질수록 Stack에 쌓여 메모리 사용량이 계속 증가한다.
  • Stack Overflow가 발생할 수 있다.

 

재귀함수 사용 예시

• 피보나치 수열, 팩토리얼 구하기
• 분할 정복 알고리즘
• 이진 탐색
• 하노이의 탑
• 백트래킹 알고리즘

 

 

Tail Recursion(꼬리 재귀)

---

Stack Overflow를 방지하기 위해 이용하는 재귀 형태다.

• 추가 연산이 없어 이전 상태를 유지할 필요가 없다
• Compiler 에서 TCO(Tail Call Optimization)을 지원해야 한다.
• Java에서는 지원하지 않는다.

Java에서 지원하지 않는 이유?

jdk 클래스에는 보안에 민감한 메소드가 있다고 한다. 이 메소드들은 메소드 호출을 누가 했는지 알아내기 위해 jdk 라이브러리 코드와 호출 코드간의 스택 프레임 개수에 의존한다. 스택 프레임 수의 변경을 유발하게 되면 이 의존관계를 망가뜨려 에러가 발생할 수 있다.

 

• 일반적인 팩토리얼 함수

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

• 꼬리재귀 팩토리얼 함수

public static int factorialTail(int n, int acc) { //acc: accumulator
    if (n == 1) 
    	return acc;
   	//일반 재귀에서의 n * factorial(n - 1)과 달리 반환값에서 추가연산이 필요없음
    return factorialTail(n - 1, acc * n);
}

-> 그러나 Java에서는 지원하지 않는다. (그저 Java 형태로 표현한 것임)

 

질문

---

Q. 재귀 함수의 동작 과정을 Call Stack을 활용해서 설명해 주세요.

• Call Stack : 현재 실행중인 서브루틴에 대한 정보들을 담아두는 스택 구조의 메모리영역
• 재귀 함수가 호출될 때마다 Call Stack에 추가한다.
• 종료 조건을 만나면 종료하고 Call Stack에서 삭제한다.