다시 알고리즘에 손대기 시작했다. 근 3일 동안 알고리즘 기초부터 공부하다가 문득 재귀를 알아두면 좋겠다 싶어서 재귀의 개념과 설계, 장 단점을 공부해봤다.

재귀 함수란?

하나의 함수에서 자신을 다시 호출 하여 작업을 수행하는 방식으로, 주어진 문제를 푸는 방법이다.

// 팩토리얼 예제)
private int factorial(int n){
	if(n == 1) return 1;
    return n * factorial(n - 1);
}

재귀함수는 언제 사용하는가?

피보나치수열이나 팩토리얼 연산과 같이 재귀적 사용이 자연스러울 때

// 피보나치 예제
private int Fibonacci(int n) 
{ 	
	if (0 == n) return 0;
	if (1 == n) return 1;
	return Fibonacci(n - 1) + Fibonacci(n - 2);
}

피보나치수열은 재귀적 사용이 자연스러워서 재귀함수를 만들어 사용하는게 더 효율적이지만 위와같은 재귀 함수는 굉장히 비효율적이다 ! Why?!?

n = 6 일때 논리 구조

만약 n이 30이라면 대략 260만번의 함수 호출이 필요하기 때문 이다.
이럴 거라면 차라리 반복문이 낫다. 그렇다고 효율적인 재귀함수를 못 만드는 것은 당연히 아니다. 글을 좀 더 내려가면 효율적인 재귀 함수 만드는 방법을 소개한다.(꼬리재귀)

재귀함수의 장점 ?

1. 이해하기 쉽다
2. 쉽게 프로그램 할 수 있다
3. 변수 사용을 줄여준다

ex. 하노이의 탑 - 반복문으로 짤시 코드가 복잡해짐

재귀함수의 단점 ?

1. 시간복잡도가 반복문에 비해 계산이 어렵다.
2. 반복문보다 큰 오버헤드를 가짐 ( 반복문보다 메모리 사용량 많고 수행 시간이 더 길어질 수 있다 )
3. 함수 호출을 많이 하기에 StackOverFlow 가능성
4. 종결조건이 A 측면, B 측면에서도 확실해야 한다. 그렇지 않으면 무한 반복이 일어난다.
5. 무한반복이 일어나는 경우 CPU 크래쉬를 초래한다.
   ( 반복문의 경우 메모리가 부족할 때가 되면 알아서 멈춤 )

꼬리재귀 - 재귀의 단점을 극복

// 꼬리재귀 피보나치의 수열 구하기
private int Fibonacci(int n){
    return FiboTail(n, 0, 1);
}
 
private int FiboTail(int n, int previous, int next){
    if (n == 0)
        return previous;
    else
        return FiboTail(n - 1, next, previous + next);
}

//꼬리재귀 팩토리얼 구하기
private int factorial(int n){
    return factorialTail(n, 1);
}
private int factorialTail(int n, int acc){
	if(n == 1) 
    	    return acc;
    return factorialTail(n - 1, acc * n);
}

일반 재귀함수는 추가 연산이 존재한다. 반면 꼬리 재귀는 함수가 두개로 분리되었는데, 재귀 호출 이후 추가적인 연산을 요구하지 않도록 구현한다.

실제로 이런 꼬리 재귀함수는 콜 스택이 추가로 생성되지 않는다 ( 원래 함수를 호출하면 콜스택이 생성된다 )

But!!
컴파일러가 꼬리재귀최적화(TCO, tail call optimization) 를 지원해 줘야 한다고 한다.
즉, 아무리 꼬리 재귀같아 보이게 설계하고 만들었다고 하더라도 컴파일러가 그 코드에 대해 꼬리재귀최적화를 지원해주지 않는다면 일반 재귀처럼 돌아간다..!!

C++, C#, Kotlin, Swift, JavaScript(ES6 스펙), Scala 에서는 꼬리재귀최적화를 지원하지만 java는 직접적으로 꼬리재귀최적화를 지원하지 않는다고한다...

결론

알고리즘 공부할 때는 맘껏 쓰더라도 실무에서는 고민에 고민을 더하자...

REFERENCE

• 재귀(Recursion) - 입코딩
• 재귀함수와 꼬리 재귀 - dldhk97