Recursion

재귀함수는 자신의 이름의 함수를 호출하면서 종료조건에 수렴해 가야한다.

그러므로 반드시 종료조건이 있어야한다. 종료조건이 없다면 무한 재귀에 빠지면서 프로그램이 종료된다.

 

재귀를 이해하기 위해서는 함수의 수행 순서를 이해할 필요가 있다. 함수가 호출 되면 스택에는 함수의 매개변수, 호출이 끝난뒤 돌아갈 반환 주소값, 함수에서 선언된 지역 변수 등이 저장됩니다. 이렇게 스택 영역에 차례대로 저장되는 함수의 호출 정보를 스택 프레임(stack frame)이라고 합니다. 이러한 스택 프레임 덕분에 함수의 호출이 모두 끝난 뒤에, 해당 함수가 호출 되기 이전 상태로 되돌아 갈 수있습니다.

 

스택프레임의 동작방식을 스택 자료구조형태로 이해하는 것은 조금 불편한 부분이 있기 때문에 트리구조의 모양으로 그려서도 설명하면 이해가 더 수훨 하기 때문에 트리형태로 설명하는 경우가 많습니다.  

우측 그림은 좌측의 코드의 실행 순서를 트리구조 형태로 표현 한것이니다.

main()이 실행되고 a()가 실행되고 반환되어 main() 으로 돌아가서 b()가 실행되고 b()에서 호출한 a()가 실행되고 다시 반환되어 b()로 돌아가고 b()에서 main()으로 돌아가서 이제 c()를 수행하고 c()에서 a()를 실행하고 수행후 c()로 돌아가서 b()를 수행하고 b()에서 a()를 호출하고 반환되면 b()로 돌아가고 c()로 돌아가고 c()를 마무리 하고 main()으로 돌아가는 순서로 함수가 실행됩니다.

 

 

피보나치함수 재귀적으로 구현