3. 재귀함수를 비재귀함수로 변환

재귀함수 장점 : 직관적인 알고리즘 설계가 가능

재귀함수 단점 : 함수 호출 오버헤드 (Context Switch) -> 시간 성능 저하, 자신을 다시 호출하면서 생성되는 변수 때문에 메모리 문제가 생길 수 있음. (출처 : http://bitly.kr/DNHtU3http://bitly.kr/DNHtU3)

-최적화 단계에서 비재귀 함수로 변환해야 함.-

1. 재귀함수와 비재귀 함수의 성능 차이

#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <time.h>

using namespace std;
//재귀함수
long long recursiveFactorial(int n) {
	if (n < 1) {
		return 1;
	}
	else {
		return n * recursiveFactorial(n - 1);
	}
}
//비재귀함수
long long nonRecursiveFactorial(int n) {
	long long f = 1;
	while (n > 0) {
		f = f * n--;
	}
	return f;
}
int main() {
	time_t start, end;
	double result;

	start = clock();	//시간 측정 시작
	cout << "Recur: "<<recursiveFactorial(20) << endl; //2432902008176640000
	end = clock();	    //시간 측정 끝
	result = (double)(end - start);
	cout << "Time:" << result << endl;                 //3

	start = clock();	//시간 측정 시작
	cout << "Non: "<<nonRecursiveFactorial(20) << endl;//2432902008176640000
	end = clock();	    //시간 측정 끝
	result = (double)(end - start);
	cout << "Time" << result << endl;                  //1
}

참고 출처 : http://wiki.gurubee.net/pages/viewpage.action?pageId=1507916

1. 재귀 호출이 하나인 경우 : 순환문으로 변환하면 됨. (위에 소스 참고)

2. 재귀 호출이 둘인 경우 : (이진트리)

 

주의점 : 비재귀함수가 항상 재귀함수보다 빠른건 아니다. (예외 케이스 찾아봐야 함)

재귀적 해법이 치명적인 예
       • 피보나치 수 구하기
       • 행렬곱셈 최적순서 구하기
재귀적 해법이 바람직한 예
       • 퀵 정렬, 병합정렬 등의 정렬 알고리즘
       • 계승(factorial) 구하기
       • 그래프의 DFS
출처: https://itance.tistory.com/entry/재귀의-문제점 [ITance]

예제) 이진트리(Binary Tree)의 순회를 재귀(recusive)방식에서 반복(iterative)방식으로 구현하기