[자료구조] 순환함수(Recursive Function)

 순환함수(Recursive Function) 개요

• 순환(Recursion) : 알고리즘이 자기 자신을 반복적으로 호출하는 과정

[사례1] 팩토리얼 계산

- n! = if (n=0) { n=1 } 

   if (n>=1) {n=nX(n-1)!}

- C로 구현한 순환함수 (스택구조 사용)

   int fact(int n)

   {

if (n<1) return (1);   //순환함수에는 반드시 종료조건이 있어야한다.

else return (n*fact(n-1));

    }

- 순환함수는 프로그램적으로는 간단하지만 내부스택을 사용하기 때문에 단점이 있다.

- 반복함수와 순환함수의 차이점

- 반복적 방법의 구현

    int fact_iter(int n)

    {

int k, v=1;

for(k=n; k>0; k--)

v=v*k;

return v;

     }

- 공간 및 시간복잡도 비교 (순환함수의 경우 내부 스택 사용)

• 순환과 반복함수 비교

- 순환함수

 1. 순환문제 : 자연스러운 코딩, 코딩이 단순하다.

 2. 스택 사용으로 인한 수행시간 오버헤드

- 반복함수

 1. 순환문제 : 코딩이 어려움

 2. 수행시간 오버헤드가 없음

- 언제 순환함수를 사용할 것인가?

 1. 코딩의 단순화 및 이해도 증진

 2. 시간 및 공간에 제약을 받지 않을 경우

[사례2] GCD (최대공약수) 계산

[사례3] 피보나치 수열의 계산

 - 오버헤드가 초래된다.

 - 따라서 반복함수로 프로그래밍해야한다.

 - 순환함수의 비효율성 : 중복계산

  1. 입력 수가 클 수록 호출횟수가 매우 크게 증가

  2. 입력이 클 경우 순환함수 구현은 비효율적

  

 

- 피보나치 수열위한 순환함수의 문제점

 : 이러한 큰 오버헤드를 초래한다.

  

 - 반복적 방법에 의한 피보나치 수열 계산

 

  

  

[사례4] 거듭제곱 계산

 - 순환적 방법이 효율적인 예

 - 숫자 x의 n 제곱값 계산 : X^n

 - 반복적인 방법

 

- 순환적인 방법

 

[사례5] 하노이 타워

 - 막대 : 3개, 원반 : n개

 - 조건 : 

1. 한 번에 하나의 원판만 이동

2. 맨 위에 있는 원판만 이동

3. 크기가 작은 원판 위에 큰 원판이 놓일 수 없음

 

[참고]

http://elearning.kocw.net/html/2012/KumOh/KimYeongHak/03/default.htm