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 까지의 합
/* 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)
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 출력
이진수로 변환하는 순환함수
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일때의 반복문이 실행되기 때문에
*
* *
* * *
* * * *
라는 결과가 나오게 된다.
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로 나타낼 수 있다.
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를 재귀적으로 비교하여 더 큰 값을 반환한다. 즉, 배열의 원소들중 최대값을 찾는 함수이다.
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]과 배열에서 그 이전 원소들의 평균을 구한다. 이 과정을 끝까지 반복하면 결국 배열 전체의 평균을 구할 수 있다.
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제곱을 반환한다.
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의 값을 증가시켜 범위를 한칸씩 오른쪽으로 이동하고 다시 교환작업을 하는 즉, 선택정렬을 하는 함수이다.