Chapter 11 함수 활용

재귀 함수 재귀 특징 함수는 함수 구현에서 자기 자신의 함수를 호출 가능 자기 자신 함수의 호출을 재귀 호출(recursive call)이라 하고, 이러한 특징을 재귀(recursion)라 한다. 재귀를 다른 말로 되부름, 또는 순환이라 표현 재귀 호출을 허용하는 함수를 재귀 함수(recursive function) 특징 구현하려는 알고리즘 자체가 재귀적 특성을 갖는다면, 재귀 함수를 이용하면 쉽게 구현이 가능 재귀 함수를 이용하면 재귀적 특성을 표현하는 알고리즘에서 쉬운 문제해결을 찾을 수 있고 이해도 쉽다. 재귀 함수는 계속적인 함수의 호출로 인하여 시간과 메모리 공간의 효율성이 떨어지는 단점 일반적으로 재귀 함수는 반복문을 이용한 함수로 변환이 가능

재귀 특성 추출 n! 수식 n!(n factorial)은 1 * 2 * 3 * … * (n-2) * (n-1) * n을 의미 계승 수식은 재귀적 특성을 갖음 즉 n!을 구하기 위해서 (n-1)!을 먼저 구한다면 쉽게 n!을 구할 수 있음 n!을 함수 factorial(n)로 구현한다면 함수 factorial(n) 구현에서 다시 factorial(n-1)을 호출하여 그 결과를 이용할 수 있음

종료 조건 함수 구현 위 소스를 기본으로, 이제 함수 factorial()을 구현하기 위해 필요한 것은 재귀적 호출이 종료되는 조건을 구하는 일 이러한 종료 조건을 고려하는 것은 재귀적 함수가 갖는 공통된 특징 재귀적 호출이 종료되는 조건이 없다면 무한 호출에 의해 문제가 발생 재귀 함수의 종료 조건을 알아보기 위해 다시 5!을 고려

n! 함수 구현 n!을 조건식으로 표현하면 다음과 같고, 이를 함수로 구현

예제 소스 factorial.c 1부터 10까지의 n!을 구하여 출력하는 프로그램  

예제 소스 Binary.c 연산 예 임의의 십진수를 이진수로 바꾸는 재귀 함수를 작성 임의의 정수를 표준입력으로 입력 받아 그 수의 이진수를 출력 입력한 수가 0이면 종료하며 0보다 크면 이진수 변환을 계속 연산 예 이진수로 변환할 십진수 6에서 6/2한 결과 값인 3은 다시 이진수를 구하기 위하여 이용 또한 십진수 6에서 6%2한 결과 값인 0은 이진수의 마지막 비트에 해당한다. 즉 이 값의 출력이 제일 마지막에 이루어져야 한다

함수 구현 지금까지 살펴본 내용을 재귀적 특성으로 표현하여 함수 binary()로 구성

함수의 인자 함수의 인자는 함수를 정의하는 곳에서 기술된 인자인 형식인자(formal parameter)와 함수 호출에서 기술된 실인자(real parameter)로 구분 형식인자에 기술된 변수는 변수의 선언과 같이 식별자의 조건에 맞는 변수 이름을 사용한다. 함수를 호출할 때는 함수의 정의에 기술된 형식인자의 수와 자료형에 맞게 실인자를 기술 형식인자의 변수는 그 함수가 호출되는 경우에 메모리에 할당(allocation)되고, 그 함수 실행을 마치면 메모리에서 자동으로 제거 (free, deallocation)

값의 의한 호출 함수의 형식 인자가 일반 변수형(기본 자료형을 의미)일 때 실제 함수가 호출되는 경우, 실인자의 값을 형식인자에 할당된 새로운 변수에 복사 저장한다. 이러한 인자의 전달 방법을 값에 의한 호출 방법(call by value) 다음 소스를 살펴보면 메인 함수에서 다른 함수 increment()를 호출하고 있다. 호출 전에는 변수 number에 10이 저장되었고, 변수 number를 실인자로 함수 increment(number)를 호출한다. 함수 호출 후 변수 number의 값은 변했을까? int main(void) { int number = 10; increment(number); printf("number = %d\n\n", number);   return 0; } void increment(int number) ++number;

값의 의한 호출 함수 메인에서의 number는 메인 함수에서만 유효한 변수이고, 마찬가지로 형식인자인 변수 number는 함수 increment() 내부에서만 의미 있는 변수 그러므로 메인에서의 변수 number와 increment()에서의 변수 number는 전혀 다른 변수 함수 increment()에서 number는 이 함수 실행이 종료되면 메모리에서 자동으로 제거 그러므로 메인 함수에서 함수 increment()가 호출되어도 메인 함수의 변수 number에는 아무런 영향을 미칠 수 없다. 그러므로 메인 함수에서 함수 호출 후 출력되는 number 변수는 여전히 10

인자와 반환 값 인자 전달 방법이 값에 의한 호출 방법(call by value)에서의 함수 인자는 함수를 호출하는 부분에서 함수를 호출하는 영역으로 자료를 전달하는데 주로 사용 반대로 호출 함수가 작업을 수행한 후, 함수를 호출한 영역으로 결과 값을 전달할 때는 반환 값(return value)을 이용

예제 소스 Callbyvalue.c 값에 의한 전달 인자를 이해

난수 임의의 수를 난수(random number)라 하는데, 시스템 라이브러리에서 난수를 만드는 함수를 제공 함수 rand()를 이용하면 난수를 발생시킬 수 있는데, 이 함수를 사용하기 위해서는 헤더 파일 stdlib.h 파일을 첨가 함수 rand()에 의해 생성되는 정수는 [0, n] 사이의 임의의 정수 여기서 n은 시스템에 따라 다르다. n은 일반적으로 헤더 파일 stdlib.h 파일에 기호 상수 RAND_MAX에 의해 정의, 다음은 Visual C++의 헤더 파일 stdlib.h 파일의 일부로서 기호 상수 RAND_MAX는 16진수로 7fff이고 십진수로 32767

0에서 32767의 난수 Visual C++에서는 함수 rand()는 0에서 32767사이의 정수 중에서 임의로 하나의 정수를 반환 함수 rand()를 이용하면 임의의 수가 발생하는데, 6개의 난수를 발생하는 프로그램을 만들어 여러 번 실행해도 항상 같은 수가 발생

시드 이용 이러한 문제를 해결하는 방법이 매번 난수를 다르게 발생시키기 위하여 시드 (seed) 값을 주는 방법 씨앗이라는 의미의 시드는 이 값을 이용하여 난수를 만드는 수식에 이용 시드 값이 다르면 함수 rand()에서 발생시키는 난수가 다르다. 난수 발생 함수 rand()에서 시드 값이 난수의 값을 결정 이 시드 값을 주는 방법은 함수 srand()를 호출 함수 time()으로 반환되는 값을 함수 srand()의 인자로 이용 함수 time(NULL)은 1970년 1월 1일 이후의 경과된 시간을 초 단위로 반환 함수 이 함수 time()을 이용하려면 헤더 파일 time.h를 첨가   난수에 시드를 주기 위해 함수 srand( time(NULL) )을 호출

예제 소스 Random.c 함수 rand()에서 시드 값을 주지 않고 6개의 난수를 발생, 출력하고, 또한 1에서 45까지의 6개의 난수를 발생시켜 출력 매번 결과가 다르도록 시드 값을 함수 time(NULL)으로 주어 1에서 45까지의 난수를 6개 발생시켜 출력

피모나츠 수 수열 피보나츠 다음 수의 나열인 수열을 살펴보면 앞의 두 수의 합이 그 다음 수 위와 같은 특징의 수열을 피보나츠(Fibonacci) 수열 피보나츠 수는 맨 처음 1202년 수학자 레오나르도 피보나츠 (Leonardo Fibonacci)에 의해 다음과 같은 문제에서 제안

피보나츠 수 위 문제에서 매달 토끼장에 있는 토끼의 쌍을 계산해 보면 위 수열로 표현됨을 알 수 있고, 이 수열을 피보나츠(Fibinacci) 수열 n번째 달의 토끼 쌍의 수를 Fn이라 하면, Fn은 다음과 같이 재귀적으로 표현 피보나츠 수를 발생시키는 프로그램을 작성한다면 재귀적 특성을 이용하여 쉽게 구현이 가능

피보나츠 구현 여기에서는 재귀적 방법이 아닌 반복적 방법을 이용하여 구현 long fibo(int n) { int fn, fn1, fn2; int i;   if (n <= 1) { return n; } else { fn2 = 0; fn1 = 1; for (i = 2; i <= n; i++) { fn = fn1 + fn2; fn2 = fn1; fn1 = fn; } return fn;

예제 소스 Fibonacci.c 피보나츠 수를 구하는 모듈을 만들어 계속적으로 수와 비율을 구해보고, 함수 fibo()를 반복 구문을 이용하여 만들어 이를 호출하여 피보나츠 수를 출력하는 프로그램 황금비 피보나츠 수의 특징 중의 하나가 연속적인 수의 비율이 1.618..의 상수 값에 수렴한다는 것 이 수는 계속 반복적으로 일어나고 황금 비(golden ratio) 혹은 황금 평균치(golden mean)라고 불린다. 놀랍게도 우리 주위에는 황금 비를 이용한 사례가 많으며, 사람들은 너비와 높이가 황금 비율인 사각형을 안정적으로 선호

하노이 탑 위 문제를 그림으로 보면 A 말뚝의 원반 64개를 말뚝 B를 이용하여 말뚝 C로 모두 옮기는 것

하노이 문제 해결 문제해결 만일 원반이 1개일 때, 바로 원반을 말뚝 A에서 C로 옮기면 된다 원반이 2개인 경우는 … 원반이 3개인 경우는 … 그렇다면 원반이 64개인 경우는 어떻게 하면 될까?

분할 정복 방법 Divide and conquer

하노이 탑 구현 하노이 탑의 분할 정복을 재귀적 함수로 구현 함수 moveHanoi(char, char, char, int)의 인자의 역할은 각각 출발 말뚝, 중간이용 말뚝, 목적 말뚝, 원반의 수 하노이 문제를 해결하려면 함수 moveHanoi(‘A’, ‘B’, ‘C’, 64)로 호출

예제 소스 Hanoi.c 하노이 탑 문제를 재귀적 함수를 이용하여 해결 하노이 탑의 원반의 수를 입력 받아 결과를 출력하는 프로그램

프로그램 연습 프로그램 목적 구현 두 개의 양의 정수를 입력 받아, 이 두 수의 최대공약수를 구하는 프로그램을 작성 두 개의 자연수의 공통인 약수를 그들 수의 공약수 그리고 이들 공약수 중에서 가장 큰 수를 최대공약수 구현 두 수의 최대공약수(Greatest Common Devisor)를 구하는 해결 방법 중에서 프로그램에서 쉽게 적용할 수 있는 방법이 유클리드 호제법 함수 호출 큰 수(max) 작은 수(min) gcd(30, 20) 20 30 % 20 == 10 gcd(20, 10) 10 20 % 10 == 0 gcd(10, 0) 그러므로 정답은 10  

함수 구현 유클리드 호제법의 원리 두 수 a, b가 있을 때, 한 수를 다른 수로 나누었을 때의 식을 고려 예를 들어 a를 b로 나누었더니 몫이 q이고 나머지가 r이었다면 a=bq+r의 식이 성립 이 때, a와 b의 최대공약수는 b와 r의 최대 공약수와 같다(r이 0인 경우에 a와 b의 최대공약수는 b가 된다)라는 것이 유클리드 호제법의 원리 예를 들어 20과 30의 최대공약수를 유클리드 호제법으로 여기서 30=20*1+10이므로 30과 20의 최대공약수는 20과 10의 최대공약수와 같다. 20=10*2+0이므로 20과 10의 최대공약수는 10이 됨을 알 수 있다. 30과 20의 최대공약수는 20과 10의 최대공약수와 같고, 그 결과는 10이므로 30과 20의 최대공약수는 10 이러한 유클리드 호제법 연산과정은 나머지 연산자 %를 이용하고, 우리가 배운 재귀 함수를 이용하면 쉽게 해결할 수 있다. 함수 호출 큰 수(max) 작은 수(min) gcd(30, 20) 20 30 % 20 == 10 gcd(20, 10) 10 20 % 10 == 0 gcd(10, 0) 그러므로 정답은 10  

함수 구현 이 유클리드의 호제법을 정리 아래에서 A는 B보다 작지 않은 수로 가정 Gcd (A, B)를 구하려면 if (B == 0) {          두 수의 최대공약수는 A이다. } else { Gcd(B, A % B)를 다시 수행한다. } int gcd(int max, int min) { if (min == 0) { return max; } else { return gcd(min, max % min); }

소스와 결과