재귀로 * n개 한 줄로 출력하기(설명) [1888 / 0760] 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가지 방향 : 하향식/상향식 단순 재귀는? 함수를 정의하는 도중에 자기 자신을 1번 호출하는 방법이다. 하향식 방법은? 큰 문제의 답을 얻기 위해서 이전에 얻어낸 같은 형태의 보다 작은 문제의 해결 결과를 이용하는 방법이다. n개의 별을 출력하는 문제는 다음과 같은 단순 재귀 하향식 방법으로 설계하여 해결할 수 있다. n개의 별을 출력하는 문제의 하향식 재귀 설계 방법(예시) - 하향식 n개의 별을 출력하는 문제는 (n-1)개의 별이 이미 출력된 상태에서 1개의 별을 더 출력하는 문제로 바꿀 수 있다. (n-1)개의 별을 출력하는 문제는 (n-2)개의 별이 이미 출력된 상태에서 1개의 별을 더 출력하는 문제로 바꿀 수 있다. (n-2)개의 별을 출력하는 문제는 (n-3)개의 별이 이미 출력된 상태에서 1개의 별을 더 출력하는 문제로 바꿀 수 있다. ... 1개의 별을 출력하는 문제는 출력된 별이 없는 상태에서 1개의 별을 출력하는 문제이다. 이렇게 어떤 큰 문제를 해결하기 위해서 바로 그 이전에 해결한 보다 작은 문제의 결과를 사용하는 설계 방법을 하향식 설계라고 생각할 수 있다. 하향식 설계는 어떤 문제를 그와 똑같은 형태의 보다 작은 문제를 해결한 결과들을 이용해 해결할 수 있도록 설계하는 방법이라고 할 수 있다. 재귀 함수를 정확하게 설계하기 위해서는 1. 가장 먼저! : 자신이 만들고자하는 “재귀 함수의 의미”를 명확하게 생각한 후, 2. 그 다음에 : “큰 문제와 작은 문제 사이의 관계(하향식)”나 “현재 상태에서 다음 상태로의 변화관계(상향식)”와 같은 관계를 분석해 작성하고, 3. 마지막에 : “가장 작은 문제 상태”나 “가장 큰 문제 상태”를 생각해 재귀 호출의 중단 조건과 그 상태에서의 리턴 값을 작성해 넣으면 된다. n개의 별을 출력하는 문제에 대해서 하향식 재귀 설계 방법을 적용해 본다면, 1. f(n)을 n개의 별을 출력해야하는 문제라고 생각(정의)한다. 그러면, f(k)는 k개의 별을 출력하는 문제이고, k개의 별을 출력하는 문제는, (k-1)개의 별이 이미 출력된 상태에서, 별을 1개만 더 출력하는 문제로 바꾸고 일반화 시킬 수 있다. 함수 호출 위치에 리턴하는 값이 없이, 함수 호출 위치로 돌아가서 이전의 재귀 호출 상태를 중단시키면 되기 때문에 void 형 함수로 설계할 수 있다. 2. 1.에서 만든 명확한 정의와 큰 문제를 보다 작은 문제로 바꾸는 관계를 이용해 함수로 작성(설계)한다. void f(int k) //k개의 별을 출력하는 문제는 { f(k-1); //(k-1)개의 별이 이미 출력하는 문제를 해결한 상태에서 printf("*"); //별을 1개 더 출력하면 된다. } //k개의 별이 모두 출력되면 함수 호출을 중단한다. 이렇게 큰 문제를 해결하기 위해, 보다 작은 문제를 해결한 결과를 이용하도록 만 작성하면 무한 재귀 호출 상태에서 빠져나오지 못하기 때문에, 재귀 호출을 중단시키기 위한 중단 조건과 처리해야할 작업을 추가로 작성해 넣어야 한다. 3. 2.에서 만든 함수에 재귀 호출 중단 조건과 리턴해야 할 값을 추가한다. 출력해야하는 별이 0개라면 더 이상 별을 출력할 필요가 없으므로, 다음과 같은 재귀 호출 중단 조건을 추가할 수 있다. (함수 호출 중단 시에는 이전 위치에 리턴하는 값이 없이, 재귀 호출을 끝내는 것이기 때문에 return; 으로만 작성하면 된다.) void f(int k) //k개의 별을 출력하는 문제는 { if(k <= 0) return; //출력해야하는 별이 0개 이하라면, 함수 호출을 중단한다. f(k-1); printf("*"); } 와 같이 어떤 상태까지만 재귀적으로 호출되는 재귀 함수를 완성시킬 수 있다. 위와 같은 생각과 함수 설계 과정을 통해, f(n)을 호출하여 n개의 별을 한 줄로 출력하는 예시코드는 다음과 같이 작성할 수 있다. #include int n; void f(int k) { if(k <= 0) return; f(k-1); printf("*"); } int main() { scanf("%d", &n); f(n); printf("\n"); } Input int 형 정수(n) 1개가 입력된다. (1 <= n <= 100) Output n 개의 * 을 한 줄로 출력한다. IO Example 입력 3 출력 ***