재귀적 함수 호출 (Recursive Function Call)

재귀적 함수 호출 (Recursive Function Call)

재귀적 함수 호출은 자기와 이름이 똑같은 함수를 다시 호출하는 것이다.

recursive function call 줄여서 recursion이라고도 한다.

 

숫자를 하나씩 내려가면서 출력하는 함수를 recursion으로 짜 보자.

 

지금 countDown 이름이 같다.

자기가 자기를 호출하는 것이다.

디버그 해보면

 

f11(Step Into) 누르면서 보면

count 는 5가 들어왔으니까

5가 출력되었다. 그 다음 다시 countDown 함수로 다시 들어간다.

count를 보면 5에서 1이 빠진 4가 들어왔다.

방금 전에 main에서 호출한 countDown이

 

여기로 올 때 5에서 1을 뺀 4를 집어넣었다.

 

지금 들어온 것은 파라미터가 다르다.

한번 더 들어온 것이다.

 

그리고 주소를 보면 위에 있는 countDown과 밑에 있는 countDown의 주소 값이 같다.

한번 더 들어가 보면

 

4가 출력되고 count는 3으로 바뀌었다.

주소도 그대로고 계속 스텝인하면

이런 식으로 나온다.

앞에서 스택과 힙 포스팅에서도 말씀드렸는데

우리가 작성한 프로그램은 메모리에 저장이 되어있다.

그리고 함수를 호출할 때는 그 메모리의 주소를 가지고 호출한다.

 

그러니까 본체는 따로 있고 잠깐 그쪽에 가서 실행시키는 개념이라고 생각하면 된다.

같다고 생각하기엔 애매하다.

countDown이 사실은 같은 코드를 따로따로 실행시키고 있는 것이라고 생각해도 된다.

용법 자체는 생각보다 간단하다.

이게 가능한 이유는 코드는 다른 데에 저장이 되어있고

함수를 호출할 때에는 주소를 보고 가는 것이기 때문이다.

어떤 함수가 메모리에서 cpu로 올라가서 cpu가 그걸 호출시키는 동안에

그냥 주소로 다른 함수를 호출시키는 건지 자기 자신을 호출시키는 건지 상관없이

그냥 호출을 하는 거라서 이런 게 가능하다.

 

이거는 좋은데 디버그 중단시키고 그냥 Ctrl + F5로 실행시키면

 

그냥 쭉 내려간다

recursion을 사용할 때에는 종료하는 조건을 반드시 만들어줘야 한다.

언제까지 호출하고 호출할지 모르기 때문에

종료 조건이 반드시 있어야 한다.

 

그리고 recursion을 너무 많이 할 때에는 스택 오버플로우가 난다.

요즘은 컴퓨터가 좋아서 많이 해도 괜찮았는데

다른 함수들끼리 호출을 하는 것은 사실 프로그래머가 손으로 짜줘야 하기 때문에

스택 오버플로우 날 정도로 부르고 부르는 것을 짜기는 어렵다.

그런데 recursion은 코딩할 때 위 예제처럼 간단하게만 짜도 자기가 자기를 부르니까 스택이 많이 쌓일 수 있다.

그래서 스택 오버플로우가 날 수 있다.

 

이 재귀 호출 말고 다른 걸로는 구현하기 어려운 알고리즘 들도 있다

그럴 경우에는 재귀 호출을 쓰셔야 하기 때문에 코딩하시면서 주의를 해야 한다.

그리고 스택 오버플로우가 두려우면 전 포스팅에서 말씀드린 것처럼 std::vector를 스택처럼 써서 막는 방법도 있다.

 

종료 조건을 만들어보자

0까지만 하는 걸로 해보자.

 

count가 0보다 클 경우에만 recursion으로 들어간다고 하면

5 4 3 2 1 0 까지 출력을 하고 끝난다.

출력을 하고 더 이상 recursion을 안 하니까

끝나고 나서 return 해서 다시 pop 해서 나온다.

countDown(2)로 바꾸고 디버거로 찍어보자.

 

이런 예제는 많이 있다.

 

조금 더 재밌는 0부터 숫자를 더해나가는 예제를 해보자.

더한 숫자를 리턴해준다.

 

이걸 바꿔줄 수 있음

 

이렇게 바꿔 쓸 수 있다.

이런 아주 흔한 예제가 피보나치 수열 출력하는 것이다.

//0 1 2 3 5 8 13 21 …

재귀 호출로 구현해보면서 연습해보자.

 

마지막으로 반복하는 것에는 recursive가 있고 iterative가 있다.

for loop에서 i는 몇 해서 몇까지 돌아가는 게 iterate 한다고 한다.

원소들을 한 번씩 다 돌면서 뭔가 작업을 하는 것을 iteration이라고 부르고

recursion은 위에서 보여드린 재귀 호출이다.

두 가지가 비슷한 듯하면서 어떻게 보면 또 명확하게 다르다.

 

recursion은 보통 구현하기 더 쉽다.

그래서 간혹 recursion으로 짜고 싶은 충동을 느낄 때가 많다.

그런데 iteration과 달리 recursion은 스택을 사용을 해야 하기 때문에

recursion에서 호출하고 호출하는 depth가 한계가 있다.

그리고 기계마다 또 다르다.

 

가급적 가능하면 iteration으로 바꿔서 사용하는 것이 좋다.

그리고 recursion을 사용하는 건 아무래도 퍼포먼스가 중요한 코드에서는 사용을 안 하는 게 좋은 것 같다.