순환함수

1. 다음 순환 함수의 반환값을 x와 y의 함수로 나타내면?

int fun1(int x, int y)
{
	if (x > y)
    	return 0;
    return y + fun1(x, y-1);
 }
 

x + (x+1) + (x+2) + ... + y
x 부터 y 까지의 합

2. 다음의 순환함수의 반환값을 n의 함수로 나타내면?

/* Assume that n >= 1 */
int fun2(int n)
{
	if(n==1)
    	return 0;
    else
    	return 1 + fun2(n/2);
 }

n = 8일때
fun2(8) = 1 + fun2(4)
fun2(4) = 1 + fun2(2)
fun2(2) = 1 + fun2(1)
fun2(1) = 0

fun2(8) = 3이므로 fun2(n) = log2(n)

3. 다음의 순환함수가 결과적으로 하는 일은?

void fun3(int n)
{
	if (n == 0)
    	return 0;
    fun3(n/2);
    printf("%d", n%2);
}

n = 8일때
fun3(8) = fun3(4) 0 출력
fun3(4) = fun3(2) 0 출력
fun3(2) = fun3(1) 0 출력
fun3(1) = fun3(0) 1 출력

이진수로 변환하는 순환함수

4. 다음의 순환함수가 결과적으로 하는 일은?

void fun4(int n)
{
	if (n > 1)
    	fun4(n-1);
    for (int i = 0; i < n; i++)
    printf(" * ");
}

1부터 n까지 개수만큼 별표를 차례대로 출력한다.
예를들어, n이 4이면 fun4(4), fun4(3), fun4(2), fun4(1)이 차례로 호출되어 콜스택에 쌓이게 되고 그 후 n이 1부터 4일때의 반복문이 실행되기 때문에

*
* *
* * *
* * * *

라는 결과가 나오게 된다.

5. 다음의 함수 fun5의 반환값을 a와 b에 관한 식으로 표현하면?

int fun(int x, int y)
{
	if (y == 0) return 0;
    return (x + fun(x, y-1));
}

int fun5(int a, int b)
{
	if (b == 0) return 1;
    return fun(a, fun5(a, b-1));
}

fun5(a,b) = fun(a, fun(a, fun(a, ...fun5(a,0))..)으로 나타낼 수 있는데 fun5(a, 0)은 1이고 fun(a,b)는 a를 b번 더하는 것이기 때문에 fun(a, fun(a, ...) 함수를 풀어가다 보면 결과적으로 fun5의 반환값은 a^b로 나타낼 수 있다.

6. 다음 함수가 결과적으로 하는 일을 최대한 간명하게 설명하라.

int fun6(int a[], int n)
{
	if(n == 1)
    	return a[0];
        
    int x = fun6(a, n-1);
    return (x > a[n-1] ? x : a[n-1];
 }

a[n-1]의 값과 그 이전 요소들중 최대값 x를 재귀적으로 비교하여 더 큰 값을 반환한다. 즉, 배열의 원소들중 최대값을 찾는 함수이다.

7. 다음 함수가 결과적으로 하는 일을 최대한 간명하게 설명하라.

double fun7(double a[], int n)
{
if (n==1) return a[0];
else
	return (a[n-1] + (n-1)*fun7(a , n-1))/n;
}

재귀적으로 호출될 때마다 배열의 마지막 원소인 a[n-1]과 배열에서 그 이전 원소들의 평균을 구한다. 이 과정을 끝까지 반복하면 결국 배열 전체의 평균을 구할 수 있다.

8. 다음 함수가 결과적으로 하는 일을 최대한 간명하게 설명하라.

int fun8(int a, int b)
{
	if (b == 0)
    	return 1;
    if (b % 2 == 0)
    	return fun8(a*a, b/2);
    return fun8(a*a, b/2)*a;
 }

재귀적으로 함수를 호출하여 b가 0이 될때까지 a를 제곱한다. 즉, a의 b제곱을 반환한다.

9. 다음 함수가 결과적으로 하는 일을 최대한 간명하게 설명하라.

void fun9(int arr[], int start_index, int end_index)
{
	if(start_index >= end_index)
		return;
	int min_index;
	int temp;

	/* Assume that minIndex() returns index of minimum value in array arr[start_index...end_index] */
	min_index = minIndex(arr, start_index, end_index);

	temp = arr[start_index];
	arr[min_index] = temp;

	fun9(arr, start_index + 1, end_index);
}

배열 arr에서 start_index부터 end_index까지의 범위에서 가장 작은 값의 인덱스를 찾아 해당 인덱스와 start_index의 값을 바꾸고 재귀적으로 start_index의 값을 증가시켜 범위를 한칸씩 오른쪽으로 이동하고 다시 교환작업을 하는 즉, 선택정렬을 하는 함수이다.