별 삼각형 출력하기(재귀)(설명) [1896 / 0768] Time Limit(Test case) : (ms) Number of users who solved : 0 Total Tried : 0 The Champion of this Problem (C++) : N/A My Best Submission (C++) : N/A [koistudy.net (T. HS Jeon 2017)] Background *주의사항 : 이 문제는 재귀 설계 문제로서 반복문을 사용한 코드는 채점이 되지 않습니다. ------ 한 정수 n을 입력받아 n층의 별 삼각형을 출력하시오. (단, 반복문은 사용할 수 없다.) 참고 프로그래밍언어에서의 재귀 함수는? - 함수를 정의할 때, 자기 자신을 호출해 사용하는 형태로 정의된 함수라고 할 수 있으며 - 3가지 종류와 2가지 방향으로 크게 구분지어 생각해 볼 수 있다. - 3가지 종류 : 단순/다중/복합 - 2가지 방향 : 하향식/상향식 복합 재귀는? 재귀 함수의 정의 안에서 다른 재귀 함수를 호출하는 형태라고 할 수 있다. 하향식 방법은? 큰 문제의 답을 얻기 위해서 이전에 얻어낸 같은 형태의 보다 작은 문제의 해결 결과를 이용하는 방법이다. n층의 별 삼각형을 출력하는 문제는 다음과 같은 복합 재귀 하향식 방법으로 설계하여 해결할 수 있다. n층의 별 삼각형을 출력하는 문제의 하향식 재귀 설계 방법(예시) - 하향식 n층의 별 삼각형을 출력하는 문제는 (n-1)층의 별 삼각형이 이미 완성되어있는 상태에서 n개의 별을 더 그려주는 문제로 나눌 수 있다. n이 4인 경우 * ** *** **** 이 형태의 별 삼각형을 f(4)라고 생각하면? * ** *** <--- 여기까지는 f(3)이다. 이렇게 f(3)이 완성되어있다면? **** <--- 별을 4개만 더 출력해 주면 된다. 이 별4개를 g(4)라고도 생각할 수 있다. n층의 별 삼각형을 출력하는 문제에 대해서 하향식 재귀 설계 방법을 적용해 본다면, 1. f(k)를 k층의 별 삼각형을 출력한 결과라고 생각(정의)한다. 그러면, k층의 별 삼각형을 출력하는 문제는, (k-1)층의 별 삼각형이 이미 출력되어있는 상태에서 k개의 별을 더 출력하는 문제로 바꾸고 일반화 시킬 수 있다. 거기에 k개의 별을 출력하는 재귀 함수를 g(k)라고 하면... 2. 1.에서 만든 명확한 정의와 큰 문제를 보다 작은 문제로 바꾸는 관계를 이용해 함수로 작성(설계)한다. void f(int k) //k층의 별 삼각형을 출력하는 문제는 { f(k-1); //(k-1)층을 출력한 다음에 g(k); //k개의 별을 출력하고, printf("\n"); //줄을 바꾸면 된다. return; //k층의 별 삼각형이 완성되었으니 끝. } 이제, 재귀 호출을 중단시키기 위한 중단 조건과 처리해야할 작업을 추가로 작성해 넣어야 한다. 3. 2.에서 만든 함수에 재귀 호출 중단 조건과 리턴해야 할 값을 추가한다. 출력해야하는 층이 0층이라면 더 이상 출력할 필요가 없으니... 다음과 같은 재귀 호출 중단 조건을 추가할 수 있다. void f(int k) //k층의 별 삼각형을 출력하는 문제는 { if(k <= 0) return; //출력해야할 층이 0층이면 그만 한다. f(k-1); g(k); printf("\n"); return; } 와 같이 어떤 상태까지만 재귀적으로 호출되는 재귀 함수를 완성시킬 수 있다. 위와 같은 생각과 함수 설계 과정을 통해, f(n)을 호출해 n층의 별 삼각형을 출력하는 하향식 복합 재귀 형태의 예시코드는 다음과 같이 작성할 수 있다. #include int n; void g(int k) { if(k <= 0) return; g(k-1); printf("*"); } void f(int k) { if(k <= 0) return; f(k-1); g(k); printf("\n"); } int main() { scanf("%d", &n); f(n); } Input int 형 정수(n) 1개가 입력된다. (1 <= n <= 30) Output n 층의 별 삼각형을 출력한다. IO Example 입력 5 출력 * ** *** **** *****