재귀 호출의 장단점

재귀함수

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

 

재귀함수 사용

• 피보나치 수열
• 팩토리얼 연산

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

 

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

 

재귀함수의 장점

• 이해하기 쉬움
• 쉽게 프로그래밍 가능
• 변수 사용을 줄여줌

 

재귀함수의 단점

• 시간 복잡도가 반복문에 비해 계산이 어려움
• 반복문보다 큰 오버헤드를 가짐(메모리 사용량이 많고 수행 시간이 더 길어질 수 있음)
• 함수 호출을 많이 하기에 StackOverFlow 가능성
• 종결조건이 A 측면, B측면에서도 확실해야 한다. 글렇지 않으면 무한 반복 발생
• 무한 반복이 일어나면 CPU 크래쉬 발생

 

꼬리재귀

• 재귀호출의 단점을 극복
• 일반 재귀함수는 추가 연산이 존재, 반면 꼬리재귀는 함수가 두개로 분리되어있고 재귀 호출 이후 추가적인 연산을 요구하지 않도록 구현
• 콜 스택이 추가로 생성되지 않음

*컴파일러가 꼬리재귀최적화를 지원해 주어야 한다.(c++, c#에서는 꼬리재귀최적화를 지원)

 

꼬리재귀 피보나치의 수열

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);
}

 

 

 

 

---

 

출처 및 참조 : https://velog.io/@osk3856/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98-%EC%9E%A5-%EB%8B%A8%EC%A0%90-%EB%B0%8F-%EA%BC%AC%EB%A6%AC%EC%9E%AC%EA%B7%80