C언어 day5 (함수 기초)

#include<stdio.h>
 
void print();        // 함수 선언
 
void main(){
 
    print();        // 함수 호출 : 함수를 호출하고 호출한 함수가 실행되면 다시 이곳으로 돌아와 이후의 명령을 수행
}
 
// 함수 정의
void print(){
    printf("함수호출\n");
}
 
 
/* function : 어떤 특정한 일을 수행하는 것
     1. 함수 종류 
        - 표준함수 : ~.h
        - 사용자 정의 함수 : 개발자의 필요에 의해 선언
     => 함수는 선처리부에 함수를 선언하고, 그 뒤에 함수를 정의, 필요할 때 함수를 호출해서 사용하면 된다 
     => 함수를 선처리부에 선언과 동시에 정의를 같이할 수 있으나, 이렇게 하면 코드가 가독성이 많이 떨어진다.
        그리고 선처리부에 선언해놓으면 헤더파일로 따로 뺄 수 있어서 나중에 include 하기만 하면됨.
    
     2. 함수 호출 및 수행 방식에는 세가지가 있다.
        call by name  : 현실적으로는 가장 좋은 방식이지만 정해진 형태로만 수행할 수 있기 때문에 한계가 있음. (정해진 데이터만 사용할 수 있기 때문에)
        call by value : 함수와 함수끼리 특정 값을 주고받으며 수행
        call by address : 메모리의 위치를 알려주면서 수행, 가장 많이 사용하는 방법 
    
     3. 형태 : 주는곳 함수이름 (받는곳) 

     4. CPU 안의 레지스터 메모리를 사용하는 것이 램(메모리)를 사용하는 것보다 속도가 빠르다 : 램을 거치지 않고 CPU 내부의 메모리인 레지스터 메모리를 바로 거치는 것이 속도가 빠름
     -> 이전에는 레지스터 메모리를 사용했었는데, 요즘은 잘 사용하지 않음
     -> 요즘은 지역변수를 램을 안쓰고 레지스터 변수를 사용하다가 다 차면 램으로 넘어감. 그래서 레지스터 변수를 따로 선언할 필요가 없음

     5. 변수 종류
        1) 전역변수 (extern variable)
        2) 지역변수 (local variable) : 변수가 속해있는 함수 내에서만 사용
        3) 레지스터 변수 : 거의 안씀
        4) 정적 변수 (static variable)
    
    6. 일반적으로 함수 호출 방법은 다음과 같다. 프로그램 실행 중 함수를 만나면 현재 위치를 저장 후, 호출할 함수의 주소로 점프해 함수 내용을 수행한다.
    함수 실행이 끝나면 기억해뒀던 원래 위치를 복귀해 다음 코드를 수행한다. (일반적으로 잦은 함수 호출로 인한 점프의 반복은 속도를 느리게 한다)
    
    7. 재귀함수의 경우 함수의 실행이 채 끝나기도 전에 자기 자신을 호출한다. 
    이게 가능한 이유는 호출된 각 함수에 대한 복귀 번지, 인수, 지역변수 등이 스택 프레임에 저장되기 때문에 기존의 작업 내용들을 서로 방해하지 않고 잘 동작할 수 있다. (Stack 방식 )
    => 함수가 콜 되면서 최근에 자신을 부른 원래 함수가 스택에 차곡차곡 쌓이게 된다. 처음 불려진 함수에서 return 되는 값이 최종 return 값.
    => 재귀 함수는 호출 시 마다 스택 공간을 이용하므로 무리하게 호출하면 스택 오버플로우가 일어날 수 있다.

    */

재귀함수 (순환)

ex) 팩토리얼, 피보나치 수열, 이항계수, 하노이의 탑, 이진탐색

# 팩토리얼 프로그래밍

int factorial(int n){

if( n==1 ) return (1);                // 순환을 멈추는 부분    : 이 부분이 없으면 시스템 오류가 발생할 때까지 무한정 호출

else return (n*factorial(n-1) );     // 순환호출을 하는 부분 

}

: 반복문은 수행속도가 빠르기 때문에 순환과 반복문은 사실 시간복잡도가 같음. 

# 거듭제곱 프로그래밍

: x의 n제곱을 구하는 함수. 순환이 반복문보다 시간 복잡도가 훨씬 작아지는 경우

double power(double x, int n){

if( n==1 ) return x;

else if( (n%2)==0 )                //짝수

return power(x*x, n/2);

else                                     //홀수

return x*power(x*x, (n-1)/2);

}

# 피보나치 수열의 계산

: 순환 호출이 더 비효율적인 예

: 피보나치 수열 http://terms.naver.com/entry.nhn?docId=2270442&cid=51173&categoryId=51173

//순환을 사용한 구현

int fib(int n){

if( n==0 ) return 0;

if( n ==1 ) return 1;

return ( fib(n-1)+fib(n-2) ); 

}

피보나치 수열의 경우 같은 항이 중복해서 계산되기 때문에 순환 호출을 사용하는 경우 비효율적이다

예를들어 fib(6)을 호출한다고 하면 fib(3)을 3번이나 중복해서 계산하게 됨 -> n이 커질수록 더 심해짐

fib(6) =     fib(5)             +             fib(4)

fib(4) + fib(3)                     fib(3) + fib(2)

fib(3) + fib(2)    fib(2)+fib(1)    fib(2)+fib(1)    fib(1)+fib(0)

// 반복 구조를 사용한 구현

fib(int n){

if( n<2 ) return n;

else {

int i, tmp, current = 1, last = 0;

for(i=2;i<=n;i++){

trmp = current;

current += last;

last = tmp;

}

return current;

}

}

# 하노이탑 

#include <stdio.h>

void hanoi(int n, char from, char tmp, char to){

if( n==1 )    printf(" 원판 1을 %c에서 %c로 옮긴다. \n", from, to);

else {

hanoi(n-1, from, to, tmp);

printf(" 원판 %d을 %c에서 %c로 옮긴다. \n", n, from, to);

hanoi(n-1, tmp, from, to);

}

}