1. 팩토리얼을 계산하는 순환호출 함수 factorial에서 매개 변수로 5를 주었다면 최대 몇 개의 factorial 함수의 활성 레코드가 동시에 존재할 수 있는가?
5개
2. 순환 호출을 하였을 경우에 활성 레코드들이 저장되는 위치는 어디인가?
④ 스택
3. 다음 중 활성 레코드에 저장되지 않는 것은 무엇인가?
④ 순환 호출의 순차번호
4. 하나의 함수가 호출할 수 있는 순환호출의 개수는?
③
5. 다음의 순환호출 함수에서 잘못된 점은 무엇인가?
int recursive(int n)
{
if( n==1 ) return 0;
return n*recursive(n); // 파라미터 값이 줄어들지 않음
}n이 줄어들지 않아 무한적으로 반복된다
6. 다음의 순환호출 함수에서 잘못된 점은 무엇인가?
int recursive(int n)
{
printf("recursive(%d)\n", n);
return n*recursive(n-1); // 순환호출 끝내는 문장 빠짐 ex) if(n==1) return 0;
}기저조건이 없다
7. 다음 함수를 sum(5)로 호출하였을 때, 화면에 출력되는 내용과 함수의 반환값을 구하라.
int sum(int n)
{
printf("%d\n", n);
if( n<1 ) return 1;
else return( n+sum(n-1) );
}5
4
3
2
1
0
반환 값 : 16
해설
sum(5) = 5+ sum4 = 16
sum(4) = 4 + sum3 = 11
sum(3) = 3 + sum 2 = 7
sum(2) = 2 + sum 1 = 4
sum(1) = 1 + sum 0 = 2
sum(0) = 1
8. 다음 함수를 recursive(5)로 호출하였을 때, 화면에 출력되는 내용과 함수의 반환값을 구하라.
int recursive(int n)
{
printf("%d\n", n);
if( n<1 ) return 2;
else return( 2*recursive(n-1)+1 );
}출력
5
4
3
2
1
0
반환 값 : 95
9. 다음 함수를 recursive(10)로 호출하였을 때, 화면에 출력되는 내용과 함수의 반환값을 구하라.
int recursive(int n)
{
printf("%d\n", n);
if( n<1 ) return -1;
else return( recursive(n-3)+1 );
}출력
10
7
4
1
-2
반환 값: 3
10. 다음 함수를 recursive(5)로 호출하였을 때, 화면에 출력되는 내용을 쓰시요.
int recursive(int n)
{
if(n != 1) recursive(n-1);
printf("%d\n", n);
}1
2
3
4
5
11. 다음 함수에서 asterisk(5)를 호출할 때 출력되는 *의 갯수는?
int asterisk(int i)
{
if( i > 1){
asterisk(i/2);
asterisk(i/2);
}
printf("*");
}******* 7개
함수가 몇번 실행되는지 알면된다.
12. 다음과 같은 함수를 호출하고 "recursive" 문자열을 입력한 다음, 엔터키를 눌럿다면 화면에 출력되는 것은?
unknown()
{
int ch;
if( (ch=getchar()) != '\n')
unknown();
putchar(ch);
}evisrucer
* getchar : 사용자가 키보드로 입력한 문자 혹은
문자열에서 한 글자를 읽어서 반환하는 함수.
* putchar : 문자를 모니터화면(콘솔)에 출력하는 함수.
// 책 오타 putchar(ch)
13. 다음을 계산하는 순환적인 프로그램을 작성하시오.
1 + 2 + 3 + ... + n
int sum(int n) {
if(n==1) return 1;
else return(n+sum(n-1));
}
14. 다음을 계산하는 순환적인 프로그램을 작성하시오.
1 + 1/2 + 1/3 + ... + 1/n
double div(int n) {
if(n==1) return 1;
else return div(n-1)+(double)1/n;
}
15. 순환 호출되는 것을 이해하기 위하여 fib 함수를 다음과 같이 바꾸어서 실행하여 보라. fib(6)을 호출할 때 화면에 출력되는 내용을 쓰시오.
fib(6) is called
fib(5) is called
fib(4) is called
fib(3) is called
fib(2) is called
fib(1) is called
fib(0) is called
fib(1) is called
fib(2) is called
fib(1) is called
fib(0) is called
fib(3) is called
fib(2) is called
fib(1) is called
fib(0) is called
fib(1) is called
fib(4) is called
fib(3) is called
fib(2) is called
fib(1) is called
fib(0) is called
fib(1) is called
fib(2) is called
fib(1) is called
fib(0) is called
해설
fib(6) = fib(5) + fib(4)
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
16.
int sum(int n) {
int ans = 0;
for(int i=0; i<=n; i++) {
ans+=i;
}
return ans;
}
17.
int bc(int n, int k) {
if (k == 0 || k == n) return 1;
else return bc(n - 1, k - 1) + bc(n - 1, k);
}18.
(a)
A(3, 2) = 29
A(2, 3) = 9
(b)
int ack(int m, int n) {
if (m == 0) return (n + 1);
if (n == 0) return (ack(m - 1, 1));
return ack(m - 1, ack(m, n - 1));
}// 책 오타 m-2 -> m-1
(c)
int ack2(int m, int n){
while (m != 0) {
if (n == 0) n = 1;
else n = ack2(m, n - 1);
m = m - 1;
}
return n + 1;
}
19.
순환 피보나치 수열은 많은 계산을 반복적으로 수행해서 수행시간이 많이 길어진다.
시간 복잡도 비교하면 반복함수는 O(n), 순환함수는 O(2^n) 이므로 반복이 더 효율적임
20.
1) n의 값이 작아진다.
2) 하나의 원판을 이동시키고 나머지 원판에 대해서 순환호출이 일어나며 작아진다.
21.
flood_fill(x+1, y);
flood_fill(x-1, y);
flood_fill(x, y+1);
flood_fill(x, y-1);동 서 남 북 으로 움직이면 됨
관심이 있으신 분들에게 유용한 정보였길 바라며
다음은 3장 핵심정리를 가져오도록 하겠습니다.