56. 재귀함수 분석

 

it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비

 

 

 

재귀함수는 Stack 이라는 자료구조를 사용한다.

 

입력값이 3일때 Recur(3),9Line - Recur(2),9Line - Recur(1),9Line- Recur(0) 순으로 함수호출위치와 함게 스택에 저장되어 Recur(0)부터 빠져나간다.

인수값이 0일때 함수는 return 하고 12라인으로 가고 다음 Recur(1)이 실행되고 함수 호출 다음문장을 실행한다. 9Line 다음인 11Line 출력함수 실행 (1출력)하고 함수 종료 Stack 빠져나간다.

이제 Stack의 제일 위에 있는 Recur(2)의 함수가 다시 실행되고 함수호출 다음 부터 위와 같이 실행을 반복하고 Stack의 바닥에 있는 Recur(3)까지 실행된다.

 

*주의사항

함수 옆에 복귀 주소line은 실제로 시스템마다 메모리의주소를 저장하는 방식에 맞게 저장된다. Line으로 표기한것은 편의상 표기함

실제로는 Recur(2)이 자신을 호출한 Recur(3)의 복귀 위치를 갖고있고, Recur(1)이 자신을 호출한 Recur(2)의 복귀 위치를 갖고있다.

 

자세한 사항은stack frame  techbook11.tistory.com/8 참조