[Algorithm] 재귀함수 분석(Stack Frame)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. N 이 주어지면

     재귀함수를 이용해서

      1 2 3 을 출력하는 것이다.

      재귀함수는 DBF, BFS 의 기본인데

      이렇게 쉬운 재귀함수문제를 버벅거리는 내 자신을 보며..

      심각성을 다시 한 번 느꼈다..

      더 분발하자..

      재귀함수는 stack 자료구조를 사용한다.

      종료지점에 도달했을 때 return 처리를 해주고 

      그렇지 않을 경우는 계속 재귀호출해주는 루틴이 제일 무난하다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include <cstdio> #include <vector> #include <algorithm>   using namespace std;   void Solution(int x) {     if (x == 0)         return;     else     {         Solution(x - 1);           printf( "%d ", x);     } }   int main(void) {     freopen("input.txt", "rt", stdin);       int n;       scanf("%d", &n);       Solution(n);       return 0; } Colored by Color Scripter

cs

#. Other code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include<stdio.h> #include<stack> #include<vector>   using namespace std;   void DFS(int x){     if(x==0) return;     else{             DFS(x-1);         printf("%d ", x);     } }   int main(){     int n;     scanf("%d", &n);     DFS(n);     return 0; }

cs

재귀함수를 눈으로 이해하기는 굉장히 헷갈리다.(나는..)

그러므로 stack 을 그려가면서 이해하는게 편할 것이다.

line 18 에서 DFS(3) 이 호출된다.

DFS 함수에 3이 들어가면 line 10까지 동작하고

DFS(3) - 10

또다시 DFS(2) 가 호출된다.

DFS(2) 도 마찬가지로 line 10까지 동작하고

DFS(2) - 10

DFS(3) - 10

또다시 DFS(1) 이 호출된다.

DFS(1) 도 마찬가지로 line 10까지 동작하고

DFS(1) - 10

DFS(2) - 10

DFS(3) - 10

DFS(0)을 호출한다.

DFS(0)은 종료지점이고 return 을 반환하였으므로

stack 에 있는 함수들을 이제 하나씩 빼보면 된다.

DFS(1) - 10

DFS(2) - 10

DFS(3) - 10

line 10 까지 진행되었던 DFS(1) 은 1을 출력,

line 10 까지 진행되었던 DFS(2) 은 2을 출력,

line 10 까지 진행되었던 DFS(3) 은 3을 출력,

이제 stack 이 비었으므로 main 함수로 돌아오게 되고 line 18 은 모두 동작하였으므로 다음 line 으로 이동한다.

무엇이든 기초가 가장 중요하다.

비록 지금은 이 쉬운 재귀함수 문제에서 버벅거렸지만

지금 기초를 잘 다져놓았으니 

앞으로 재귀함수 관련된 다른 문제들은 잘 해결해낼 수 있을 것이다 !!

#. For Interview 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include<stdio.h> #include<stack> #include<vector>   using namespace std;   void DFS(int x){     if(x==0) return;     else{             DFS(x-1);         printf("%d ", x);     } }   int main(){     int n;     scanf("%d", &n);     DFS(n);     return 0; }

cs

프로그램이 실행되면 main()함수가 호출되는데,

함수는 호출이 되면 stack에 자신의 호출 정보를 기록하게 된다. 

호출 정보가 기록된 것들을 stack frame이라고 부른다.

프로그램이 실행되면 먼저 main()함수의 stack frame이 stack에 저장될 것이다.

메인 함수의 stack frame은 아래 그림과 같다

여기서 line 18에서 DFS(3)함수를 호출하게 되면

아래 그림과 같이 DFS(3)의 stack frame이 stack에 쌓이게 된다.

복귀 주소는 컴퓨팅 언어로 저장되어있을 것이다. (아래 그림은 사람 눈에 보기 쉽게 표시해놓았지만..)

DFS(3)에서 다시 재귀함수를 호출하면

또 아래 그림과 같이 DFS(2)의 stack frame이 stack에 쌓이게 된다.

여기서 체크해야할 부분은

Stack frame이 무엇인지를 알아야 한다는 점!

#. Result

  - Input --------------------------------------------------------

3

------------------------------------------------------------------

  - Output --------------------------------------------------------

1 2 3

------------------------------------------------------------------