재귀함수

언젠가 한번 공부해야지 하고 밀어두다고 씨름로봇하면서 평균필터 재귀함수로 작성해야될 일이 생겨서 공부한다.

재귀함수, 순환함수, Recursion 이라고도 한다. 사용법은 간단하다. 팩토리얼 재귀함수를 예로 들어본다.

< 팩토리얼 재귀함수 >

재귀함수는 반드시 두부분으로 나뉘어야 한다.빨간색 부분은 이 재귀가 드디어 멈추는 구간이다. 반드시 멈출 수 있는 조건을 작성해 주어야 한다. return 부분에 초록색 동그라미는 바로 재귀호출을 하고 있는 문장이다.

구체적인 함수흐름

< 함수 흐름도 >

자기 자신을 호출한다고 하지만, 실제로 동작 순서는 위와 같다. 재귀함수를 이해할 때는 항상 위와 같은 그림을 연상하는게 정신건강에 이롭다. 

효율성

반복문과 재귀함수 효율은 어떨까? 아무리 찾아봐도 재귀함수가 효율이 좋다는 말은 없다. Stack Overflow 라는 것이 있는데 함수가 호출 될 때 스택 메모리를 사용한다. 재귀호출은 함수가 꼬리에 꼬리르 물고 실행되기 때문에 계속해서 메모리에 쌓이게 된다. 그렇다보니 시간과 메모리공간의 효율성이 떨어지는 단점이 있다. 특히 피보나치 수열같은 함수를 재귀함수로 사용하게되면 스택을 기하급수적으로 증가시키기 때문에 매우 비효율 적이다.

< 피보나치 수열 >

마지막에 return fibo(n-1) + fibo(n-2); 이부분에서 각 함수자체가 또 재귀를 또또또........ 호출한다.