[C언어로 쉽게 풀어쓴 자료구조] 2장

01 팩토리얼을 계산하는 순환호출 함수 factorial에서 매개 변수로 5를 주었다면 최대 몇 개의 factorial 함수의 활성 레코드가 동시에 존재할 수 있는가?

 

02 순환 호출을 하였을 경우에 활성 레코드들이 저장되는 위치는 어디인가?

(1)순환호출 함수 내부

(2)변수

(3)배열

(4)스택

 

03 다음 중 활성 레코드에 저장되지 않는 것은 무엇인가?

(1) 매개변수의값

(2)함수 호출이 끝나고 복귀할 주소

(3)지역변수

(4) 순환호출의 순환번호

 

04 하나의 함수가 호출할 수 있는 순환호출의 개수는?

(1)1번

(2)2번

(3)스택이 허용하는 한도

(4)무제한

 

05 다음의 순환호출 함수에서 잘못된 점은 무엇인가?

int recursive(int n)
{
	if(n==1) return 0;
    return n*recursive(n);
}

 06 다음의 순환호출 함수에서 잘못된 점은 무엇인가?

int recursive(int n)
{
	printf("recursive(%d)\n", n);
    return n*recursive(n-1);
}

07 다음 함수를 sum(5)로 호출하였을 때, 화면에 출력되는 내용과 함수의 변환값을 구하라.

int sum(int n)
{
	printf("%d\n",n);
    if(n<1) return 1;
    else return (n+sum(n-1));
}

08 다음 함수를 recursive(5)로 호출하였을 때, 화면에 출력되는 내용과 함수의 반환값을 구하라.

int recursive(int n)
{
	printf("%d\n,"n);
    if(n<1) return 2;
    else return (2*recursive(n-1)+1);
}

 

09 다음 함수를 recursive(10)로 호출하였을 때, 화면에 출력되는 내용과 함수의 반환값을 구하라.

int recursive(int n)
{
	printf("%d\n,"n);
    if(n<1) return -1;
    else return (recursive(n-3)+1);
}

10 다음 함수를 recursive(5)로 호출하였을 때, 화면에 출력되는 내용을 쓰시오.

int recursive(int n)
{
    if(n!=1) recursive(n-1);
    printf("%d\n",n);
}

11 다음 함수에서 asterisk(5)를 호출할 때 출력되는 *의 갯수는?

void asterisk(int i)
{
	if(i>1){
    asterise(i/2);
    asterisk(i/2);
    }
    printf("*");
}

12 다음과 같은 함수를 호출하고 "recursive" 문자열을 입력한 다음, 엔터키를 눌렀다면 화면에 출력되는 것은?

unknown()
{
	int ch;
    if(ch=getchar())!='\n')
    	unknown();
    putchar();
}

13 다음을 계산하는 순환적인 프로그램을 작성하시오.

1 + 2 + 3 + ... + n

 

14 다음을 계산하는 순환적인 프로그램을 작성하시오.

 

1 + 1/2 + 1/3 + .. + 1/n

 

15 순환 호출되는 것을 이해하기 위하여 fib 함수를 다음과 같이 바꾸어서 실행하여 보라. fib(6)을 호출할 때 화면에 출력되는 내용을 쓰시오.

int fib(int n)
{
	printf("fib(%d) is called\n",n);
    if(n==0) return 0;
    if(n==1) return 1;
    return (fib(n-1) + fib(n-2));
}

16 다음의 순환적인 프로그램을 반복 구조를 사용한 비순환적 프로그램으로 바꾸시오.

int sum(int n)
{
	if(n==1) return 1;
    else return (n+ sum(n-1));
}

 

17 이항게수 binomial coefficient)를 계산하는 순환함수를 작성하라. 이항계수는 다음과 같이 순환적으로 정의된다. 반복함수로도 구현해보라

18 Ackermann 함수는 다음과 같이 순환적으로 정의된다. 

A(0,n)=n+1;

A(m,0)=A(m-1,1)

A(m,n)=A(m-2,A(m,n-1))    m, n≥1

 

(a)A(3, 2)와 A(2, 3)의 값을 구하시요

(b)Ackermann 함수를 구하는 순환적인 프로그램을 작성하시요

(c) 위의 순환적인 프로그램을 for, while, do와 같은 반복구조를 사용한 비순환적 프로그램으로 바꾸시요.

 

19 본문의 순환적인 피보나치 수열 프로그램과 반복적인 피보나치 수열 프로그램의 수행 시간을 측정하여 비교하라. 어떤 결론을 내릴 수 있는가?

 

20 순환호출에서는 순환호출을 할때마다 문제의 크기가 작아져야한다.

(1) 팩토리얼 계산 문제에서 순환호출이 일어날 때마다 문제가 어떻게 작아지는가?

(2) 하노이의 탑에서 순환호출이 일어날 때마다 문제의 어떻게 작아지는가?

 

21 컴퓨터 그래픽에서의 영역 채우기 알고리즘은 순환 기법을 사용한다. 영역 채우기란 다음과 같은 흰색 영역이 있을 때 이 영역을 특정한 색으로 채우는 것이다. 여기서는 이 영역 안쪽을 검정색으로 채운다고 가정해보라. 이런 경우에는 순환 호출을 어떻게 사용할 수 있을까? 2차원 배열이 다음과 같이 되어 있다고 가정하고 영역안의 한 점의 좌표가 주어졌을 경우에 안쪽을 채우는 순환 호출 함수를 작성하여 보라.

[그림 2-16]의 x로 표시된 픽셀이 시작 픽셀이다.

Hint

위의 문제를 해결하려면 먼저 위의 [그림 2-16] (a)를 2차원 배열을 이용하여 (b)와 같이 나타낸다. 노란색은 2로, 흰색은 0으로 영역을 표시한 다음, 0의 값을 갖는 픽셀을 전부 1로 바꾸면 되는 것이다. 다음 프로그램의 빈칸을 채운 다음, 수행시켜서 어떤 순서대로 채워지는 지를 살펴본다.

 

#define WHITE 0
#define BLACK 1
#define YELLOW 2

int screen[WIDTH][HEIGH];
// 
char read_pixel(int x, int y)
{
	return screen[x][y];
}
//
void write_pixel(int x, int y, int color)
{
	screen[x][y]=color;
}
//영역채우기 알고리즘
void flood_fill(int x, int y)
{
	if (read_pixel(x,y)==WHITE)
    {
    	write_pixel(x,y,BLACK);
        ;//순환호출
        ;//순환호출
        ;//순환호출
        ;//순환호출
	}
}