[알골90제] 56번 - 재귀함수 분석 : STACK 이용

*문제

 

자연수 N이 주어지면 재귀함수를 이용해서 아래와 같이 출력하시오.

스택을 이용하는 재귀함수

 

입력

3

 

출력

1 2 3

 

 

*코드구현

 

// 56번 - 재귀함수 (기본)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

//반환하는 건 아니고 출력함수라서 void
void recur(int x) {

	if (x == 0) return; //종료지점
	else {	
		recur(x - 1);
		printf("%d ", x);
	}
}

int main() {

	int n;
	scanf("%d", &n);
	recur(n);

}

 

 

* 주의!

//recur과 printf의 순서를 바꾸면 

//1 2 3 => 3 2 1 됨
//c언어는 stack을 이용해서 재귀하기때문

 

 

D(3) - 9라인까지 했다고 스택에 저장

D(2) - 9라인까지 했다고 스택에 저장

....

=> 9라인에서 재귀되니깐

 

 

함수가 자기 할 일을 다 했다면 스택에서 빠져나간다.

스택에 있는 최 상단에 있는 것들이 실행된다.

 

D(1) - 9 라인까지 했으니, 10라인인 printf 이후 마저 끝내고 스택에서 빠져 나감