[자료구조 2장] - 프로그래밍 기초(2)

프로그래밍 기초(2)

 

함수와 재귀호출

C프로그래밍은 함수들의 모임과 활용으로 구성

표준 입출력 함수 : printf / scanf => 표준 라이브러리에 작성되어 있는 함수 활용

라이브러리 사용 -> 함수의 정의를 포함하는 헤더파일을 include 시켜야함

 

개념

- 함수의 원형

- 함수의 정의

- 매개변수

- 값에 의한 호출

 

함수의 원형 : 함수 반환값의 형(type)과 함수이름(function_name), 각 매개변수의 형과 이름을 포함

type function_name(type1 parameter1, type2 parameter2, .... typeN parameterN)

 

재귀함수(recursive function)

int my_pow(int x, int y);

void main()
{
    int k;
    for(k = 2; k < 6; k++)
    	printf("%d ** %d = %d\n", k, k+1, my_pow(k, k+1));
}

int my_pow(int x, int y)
{
	int i, ans = 1;
    for(i = 0; i < y; i++)
    	ans = ans * x;
    return ans;
}

위 스크립트를 실행하면 my_pow(2, 3), my_pow(3, 4), my_pow(4, 5), my_pow(5, 6) 을 실행하게 됨

 

함수를 정의하고 매개변수를 입력으로 호출하여 실행하는 특별한 경우로 재귀호출 함수가 있다.

재귀란 스스로 다시 돌아온다는 뜻으로 함수애서 자기 자신을 다시 호출하여 문제를 해결하는 방법이다.

 

팩토리얼을 구하는 재귀함수

int factorial (int n)
{
    if(n <= 1)
    	return 1;
    else
    	return n * factorial(n-1);
}

 

 

피보나치 수열을 구하는 재귀함수

int fibo(int n)
{
    if(n == 0 || n == 1)
    	return 1;
    else
    	return(fibo(n-2) + fibo(n-1));
}

 

유클리드 호제법(알고리즘) : 두 정수의 최대공약수를 구하기 위한 알고리즘

최대공약수(greatest common divisor) -> gcd

재귀함수, 반복문으로 구현 가능

int gcd(int x, int y)
{
    if(y == 0)
    	return x;
    else
    	return gcd(int y, int x%y);
}

ex) x, y에 56, 16을 넣으면, gcd(56, 16) -> gcd(16, 8) -> gcd(8, 0) => x출력(최대공약수 8)

 

유클리드 호제법을 이용한 최소공배수 구하기

최소공배수(least common multiple) -> lcm

최소공배수 * 최대공약수 = 두 자연수의 곱

최소공배수 = 두 자연수의 곱 / 최대공약수

int lcm(int x, int y)
{
    return x * y / gcd(x, y);
}

 

이진트리의 정의

이진트리 : 비어있거나 루트와 왼쪽 서브트리, 오른쪽 서브트리 2개의 분리된 이진트리로 구성된 노드의 유한집합

- 왼쪽, 오른쪽 서브트리도 이진트리이다.
- 재귀적인 성질을 가진다.

 

이진트리의 순회

typedef struct tnode * Tpointer;
struct tnode {
    char data;
    Tpointer left_stree, right_stree;
};


void itraverse(Tpointer root)
{
    if(root)
    {
    	itraverse(root->left_stree);
        printf("%c  ", root->data);
        itraverse(root->right_stree);
    }
}

위 스크립트는 재귀호출을 사용하는 이진트리의 중위순회 코드이다.

구조체를 통해 data와 Tpointer left, right를 선언하고, itraverse함수에서 left부터 순회하기 시작한다.

이진트리 예제이미지

위와 같은 이진트리에 해당 순회를 실행시켜 보면, 가장 왼쪽부터 순회하므로, D B E H A F C I G 순서대로 나오게 된다.