C++ 재귀함수

재귀함수

재귀함수는 함수 안에 자기 자신을 호출하는 것을 말한다.

가독성 , 구현의 용이하다.

 

그러면 한번 함수 안에 자기 자신을 호출해보자.

Factorial 함수에 Factorial를 호출해 보았다.

그런데 오버플로라는게 발생하였다.

그 이유는 함수안에 함수를 계속 호출하여서 스택이 더 이상 쌓을 수 없어서 발생하는 것이다.

오버플로는 재귀함수를 사용할 떄 가장 나타나는 대표적인 오류이다.

그래서 재귀함수를 사용할떄에는 탈출할수 있게 해줘야한다.(if문)

 

재귀함수를 함수를 사용해보자

Factorial_Re(5)를 불렀습니다.

if 문 5 에 안걸려서 5*Factorial_Re(4) 리턴을 할 때 함수가 또 호출이 되었기 때문에 아직 반환이 되지 않고 스택에 머뭄

그 다음에 4*Factorial_Re(3) -> 3*Factorial_Re(2) -> 2*Factorial_Re(1) -> Factorial_Re(1)이 불려 if문에 걸려 1을 리턴해준다. 그 다음에 이제 거꾸로 올라가 계산 되지 않은 값을 계산해준다. 계산이 안된 값을 실행해준다.

factorial_Re(1)          = 1  을 반환하면서 종료

factorial_Re(2) = 2 * 1  = 2  을 반환하면서 종료

factorial_Re(3) = 3 * 2  = 6  을 반환하면서 종료

factorial_Re(4) = 4 * 6  = 24 을 반환하면서 종료

factorial_Re(5) = 5 * 24 = 120 을 반환해주며 최종적으로 120이 나온다.

 

재귀함수 안쓰고 for으로 구현하는 방법

이렇게 할수도 있다.

 

다른 예)피보나치 수열

 

재귀함수로 간단하게 피보나치 수열을 구현해보았다.

 

재귀 안쓰고 for문으로 구현

이렇게 재귀함수는 코드가 이쁘고 구현은 쉽다. 하지만 피보나치 50을 요청을 해보자 그러면 함수호출이 너무 많아져 시간이 엄청오래 걸릴것이다. 그러므로 적절하게 사용할 필요가 있다.

 

출처 : https://www.youtube.com/c/AssortRockGameAcademy