[Algorithm] 재귀 (Recursion)

 

[Algorithm] 재귀 (Recursion)

 

 

재귀(recursion) 란?

재귀로 문제를 푼다는 것은 하나의 함수에서 다시 자기 자신을 호출해 문제를 해결해 나가는 것을 말한다. 자기 자신을 다시 호출할 때, 보통 인자를 더 작게 해주며 호출해주며 인자 or 함수값이 일정 값 이하일때 반복을 종료 해줄 수 있도록 조건을 추가해 준다. 이런 하위 문제를 base condition이라고도 한다. 예를 들어 아래와 같다.

 

#include <iostream>

using namespace std;

void recursion(int arg) {
	cout << arg << endl;
	if (arg == 0) return;
	recursion(arg - 1);
}

int main(void) {
	recursion(5);
	return 0;
}

/* result
5
4
3
2
1
0
*/

 

위와 같은 경우 recursion 함수가 자기 자신을 호출한다. arg 인자를 1씩 줄이면서 넘겨주고, arg가 0이면 return 한다. 따라서 5, 4, 3, .. 이 출력되다가 0까지 출력되고 (arg == 0) 조건을 만나 종료한다. 즉 arg = 0이 base condition이다.

 

재귀를 굳이 쓰지 않고 반복문으로 문제를 풀 수도 있다. 재귀를 씀으로써 얻는 장점은 코드가 간결해지고 이해하기 쉽다는 것이다. 하지만 재귀를 쓰게 되면 반복문보다 메모리/시간면에서 손해를 본다는 단점이 있다. 피보나치 수열이 재귀로 해결하면 안되는 대표적 예다. 재귀로 풀게 되면 k번째 항을 O(1.6의 k승)에 풀 수 있지만 피보나치 수열은 O(k)로도 충분히 풀어낼 수 있다. 또한 sw expert academy와 같은 문제 풀이 사이트에선 스택 메모리를 1MB로 제한하는데 이는 재귀를 쓰게 되면 너무 쉽게 넘어버리기 때문에 사용을 자제하는 것이 좋다.

 

 

 

 

 

 

참고

 

blog.encrypted.gg/731?category=773649