본 문제는 C 의 빠른 기초 학습을 위해 설계된 문제로서 C 코드 제출을 기준으로 설명되어 있습니다.
——

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

한 정수 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층의 * 삼각형을 출력한다.

기초100제(c)2 v1.0 : 정보교사 커뮤니티 @컴퓨터과학사랑(CSL)
– 중고등학교 정보 선생님들과 함께 정보수업/방과후/동아리활동 등을 통해 재미있게 배워보세요.
– 모든 내용 및 이미지들은 저작자와의 협의 없이 무단으로 사용할 수 없습니다.