[알고리즘] 재귀(recursion)

재귀 함수

함수 안에서 자기 자신을 다시 호출하는 함수

 

재귀 함수 장점

복잡한 알고리즘을 가독성있게 표현할 수 있다.

재귀 함수 단점

함수 호출 오버헤드가 크다

 

재귀 함수 주의점

무한 루프에 빠지지 않기 위해 종료 조건을 잘 처리해야한다.

 

재귀 vs 반복문

모든 재귀 호출은 반복문으로 표현 가능하고

모든 반복문은 재귀 호출로 표현 가능하다.

 

재귀 코드

long long recursive(int n) {
	if (n < 1) 
		return 1;
	else 
		return n * recursiveFactorial(n - 1);
}

반복문 코드

long long nonRecursive(int n) {
	long long f = 1;
	while (n) 
		f = f * n--;
	return f;
}

 

 

참고 사이트

https://ansohxxn.github.io/algorithm%20lesson%201/chapter1-1/