[재귀알고리즘]재귀함수를 쓰는 이유

for문, while문을 이용할 수 있는데 왜 재귀함수를 사용하는가?

 

1. 재귀함수를 쓰는 이유

1. 알고리즘 자체가 재귀적으로 표현하기 자연스러울 때 (가독성)
2. 변수 사용을 줄여 프로그램 오류 가능성을 줄여준다. 

 

1번은 말 그대로 재귀적으로 표현하는 코드가 알맞은 경우를 의미한다. 

2번의 경우, 변수 사용을 줄여준다는 건 변수가 잡는 메모리에 대한 이야기가 아니라(재귀함수는 메모리를 많이 차지하며 반복문에 비해 성능이 느리다.) mutable state(변경가능한 상태)를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄인다는 이야기다.

 그렇다면 앞서 말한 재귀함수의 "메모리를 많이 차지하며 반복문에 비해 성능이 느리다"는 문제점을 해결하기 위해서는 어떻게 해야 할까.

 

2. 재귀함수의 문제점 해결방법

재귀함수의 문제점 해결방법은 재귀함수를 구현할 때 꼬리재귀를 제거하고 개발하는 것이다. 아래 두가지 코드가 있다.
일반적인 재귀함수에서 마지막 recur(n-2)를 제거하고 n= n-2로 업데이트할 수 있도록 구현하여 기존 재귀의 문제였던 메모리와 성능에 대한 문제를 제거 할 수 있다. (단, 컴퍼일러가 꼬리 재귀 최적화를 지원하지 않으면 개발자가 꼬리 재귀방식으로 개발해도 성능 및 메모리의 이점을 없을 수 없다.) 

// 일반적인 재귀함수
static void recur(int n){
	if(n<0){
    	recur(n-1);
        System.out.println(n);
        recur(n-2);
    }
}

// 꼬리 재귀를 제거한 함수
static void recur(int n){
	if(n<0){
    	recur(n-1);
        System.out.println(n);
        n = n-2;
    }
}

 

 

자료출처:medium.com/sjk5766/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EB%A5%BC-%EC%93%B0%EB%8A%94-%EC%9D%B4%EC%9C%A0-ed7c37d01ee0medium.com/sjk5766/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EB%A5%BC-%EC%93%B0%EB%8A%94-%EC%9D%B4%EC%9C%A0-ed7c37d01ee0