[C++] Recursion | 재귀호출

Recursion

재귀호출

- 함수가 자기 자신을 호출하는 기능이다.
- C와 달리, C++에서는 \(\texttt{main()}\) 함수의 재귀호출은 허용하지 않는다.
- 반복되는 연쇄 호출을 끝내기 위해 일반적으로는 \(\texttt{if}\) 구문을 재귀 호출의 일부로 만든다.
- 하나의 작업을 서로 비슷한 두 개의 작은 작업으로 반복적으로 분할해가면서 처리해아 하는 상황에 적합하다.
(특히, 이런 상황에서의 재귀적 접근법을 "Divide & Conquer" 전략이라고 부른다.)
(재귀호출의 횟수가 계속해서 2배씩 증가하기 때문에 재귀 호출의 단계가 많이 요구되는 경우엔 오히려 비효율적일 수 있다.)

Ex. 재귀함수의 일반적인 형태

returnType Func (arguments) {
    Statement_1
    if (test)
        Func(argument);
    Statement_2
}

- \(\texttt{if}\) 구문이 \(\texttt{true}\)로 유지되는 동안, 각각의 \(\texttt{Func(argument)}\) 함수 호출 구문은 \(\texttt{Statement_1}\) 부분만 수행하고 \(\texttt{Statement_2}\) 부분은 유보한채 \(\texttt{func(argument)}\) 재귀호출이 끝나게 되면 가장 마지막에 호출된 \(\texttt{Func(argument)}\)함수의 \(\texttt{Statement_2}\)구문부터 시작해서 가장 처음에 호출된 함수의\(\texttt{Statement_2}\) 구문을 수행하고 본 재귀함수를 마치게 된다.
- 각각의 재귀 호출은 자신만의 변수 집합을 메모리 내에 따로 만들게 된다. 그러므로 \(n\) 번은 재귀 호출이 일어났다면, 변수 집합이 \(n\)번 만들어진다.