1201: [기초-재귀설계] * 삼각형 출력하기(재귀)(설명)

*주의사항 : 이 문제는 재귀 설계 문제로서 반복문을 사용한 코드는 채점이 되지 않습니다.
------

한 정수 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 <stdio.h>

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);
}

int 형 정수(n) 1개가 입력된다.
(1 <= n <= 30)

n층의 * 삼각형을 출력한다.

5

*
**
***
****
*****