함수는 호출될 때 자신이 가지고 있는 지역 변수와 매개변수를 저장하는 공간을 메모리에 할당받게 되며 이를 스택 프레임이라 부릅니다.
예컨대 아래와 같은 구조의 함수가 있을 때 A()를 실행했다면 현재 호출된 함수 A의 지역 변수인 x와 y의 값인 4와 6을 스택 프레임에 저장하게 되며, A 내부에서 B()가 호출되면 B를 위한 스택 프레임이 생기게 됩니다.
이 때 중요한 점은 아까 실행된 A가 가지고 있던 x와 y의 값은 스택 프레임 안에 그대로 보존된다는 점입니다. 자료구조 스택을 공부하셨다면 이해하기 쉬울텐데, 스택의 top에 A의 정보가 있던 상황에서 B가 호출되며 B의 정보가 스택에 push 되었고 스택의 top은 이제 B의 정보를 보여주는 상황인 겁니다.
이제 B가 종료하면 pop하며 아까 가지고 있던 A의 정보가 "그대로" 드러납니다. 아래 코드를 실행해보시면 x=4, y=6이 출력되는 것을 확인하실 수 있습니다.
이제 재귀 함수로 간다고 해서 이게 달라지지 않습니다.
BT가 BT를 호출한다고 해서 '같은 함수니 변수의 내용을 공유한다' 같은 상황은 일어나지 않습니다. 예컨대 k번째로 실행된 BT(idx)가 39번 줄에서 int prev = 0; 이 실행되었고, 44번 줄에서 prev = arr[i];가 실행되며 값이 바뀌었으며 47번 줄에서 BT(idx+1); 이 호출되면서 엄청 많은 횟수의 재귀 호출이 이뤄졌다고 합시다.
스택 프레임의 관점에서 47번 줄이 실행된 순간 원래 가지고 있던 prev 값인 arr[i] 값을 그대로 보존한 상태에서 스택의 위에 다른 정보들이 push됩니다. 함수 호출이 많이 될테니 그 위로 push와 pop이 아주 많이 일어나겠지만 스택 아래에 있던 값은 변하지 않으니 prev는 아까 들고 있던 arr[i] 값을 계속 보존하고 있습니다.
자, 기나긴 재귀가 끝나고 아까 실행했던 "그" 47번 줄이 끝났습니다.
그러면 이제 원래의 스택 프레임에 돌아왔고 40번 줄의 for문에서 i가 더해진 후 다시 만나는 42번 줄에서 prev 값은 아까의 그 arr[i] 값입니다. 0이 아니라요.
설명이 좀 중구난방인데, 비유하자면 이런 겁니다.
책상에 종이 한 장을 올립니다.(종이를 올린다 = 함수 호출)
그 종이에 "prev = 3" 이라고 쓴 뒤에 그 위에 종이를 올립니다. (재귀 함수 호출)
방금 올린 그 종이에 "prev = 5"라고 쓴 뒤에 그 종이를 다시 치웁니다. (종이를 치운다 = 함수 종료)
그러면 종이에는 뭐가 쓰여있을까요?
"prev = 3"이라 쓰여있을 겁니다. 원래 값이 남아있죠.
함수 호출은 항상 종이를 올린 "후에" 거기에 무언가를 쓰는 과정이기 때문에 원래 종이는 달라지는 게 없는 겁니다.
ehdgud583205 2년 전
39행에 int prev=0; 이면
재귀를 호출할때 마다 prev=0으로 초기화되어서
42행의 prev != arr[i]를 항상 충족하게 되어 정답이 나오지 않지 않나요??
재귀에 대한 이해가 아직 많이 부족한 것 같네요
고수행님들 설명좀 부탁드립니다~