재귀함수 언제 쓰면 좋을까?

재귀적 호출(Recursive call)란

function recursion () {
  console.log("This is")
  console.log("recursion!")
  recursion()
}

일정 조건을 만족할 경우 자기 자신을 호출하는 하는 것을 말합니다. 이를 구현한 것을 재귀 함수라 한다. 반복문 과 유사하긴 한데 도대체 언제쓰면 좋고 쓰지말아야 할때는 언제인가? 하는 궁금증이 생겼습니다.

재귀 함수의 장점

1,변수를 여럿 만들 필요가 없다.
예를들어 현재 상태를 저장해야 할 경우 tmp 변수를 만들기보다 상태를 메서드를 재귀적으로 호출하면서 변경된 상태를 전달 함으로써 변수의 수를 줄일 수 있다.
2, 반복문을 좀더 간결하고 쉽게 코드를 짜서 해결할수 있다.

이럴때 사용 하지마!

public class RecursiveCall2{
    
    public static void main(String [] args){
        int result = recursiveCall(5);
 		System.out.println(result);
    }
    
    public static int recursiveCall(int n) {
    	if(n == 1) {
            return n;
        } else {
            return n + recursiveCall(n-1);
        }
    }
}

위에 함수 결과는 나오게 되겠지만 스택 메모리에 리턴 값,매개변수 ,지역변수 들의 값이 저장이 되면서 메모리를 많이 차지하며 스택 오버 플로우가 발생할수도 있다.

스택오버플로우

재귀 호출이 무한히 반복되거나 호출 횟수가 매우 많아질 경우, 스택 메모리에 계속해서 스택 프레임이 쌓이게 됩니다. 스택 메모리의 한계를 초과하게 되면 스택 오버플로우 오류가 발생합니다. 이처럼 종료조건 을 확실하게 하지 않으면 오류가 발생하기 때문에,방지하긴 위해선 재귀함수의 종료조건을 확실시 시켜주고반복문으로 대체 가능한 경우에는 재귀함수 보다 반복문이 좋다.

재귀 함수의 단점 해결 방법

꼬리 재귀(tail call recursion)의 최적화

재귀 함수의 가장 큰 문제가 자기 자신을 호출한 뒤 결과를 기다리면서 생기는 콜스택의 부하로 인한 메모리낭비였는데, 꼬리 재귀라는 개념을 이용하면 재귀 호출이 끝나는 시점에서 아무 일도 하지 않고 바로 결과를 반환하도록 하는 방법으로 함수의 상태 유지 및 추가 연산을 하지 않기에 스택 오버 플로우 해결할 수 있다.

java
// Basic Recursion
int factorial(int n, int total) { 
    if (n === 1) { 
        return 1; 
    } 
    return n * factorial(n-1);
}

// Tail Recursion
int factorial(int n, total) {
    if (n === 1) { 
        return 1; 
    } 
    return factorial(n - 1, n * total);
}

차이점 을 보면, 반환부분의 연산이 사라졌다. 꼬리재귀의 핵심은 반환부분에 연산이 없어야 한다는 점이다.이렇게 반환부에 연산이 없도록 구현을 한다면 컴파일러는 꼬리 재귀 최적화를 지원하여 자체적으로 재귀함수를 해석해서 반복문으로 변경해서 실행한다.