순환(재귀)

2장 순환(재귀)

- 정리의 기반은 학교 강의 노트와 [c언어로 쉽게 풀어쓴 자료구조]를 참고하였습니다.

저의 정리가 옳지 않다면 피드백 부탁드립니다.

---

순환에서의 키워드

활성 레코드 : 시스템 스택에 만들어지며, 복귀 주소, 매개변수, 지역변수 등이 기록된다.
- 순환에서는 알고리즘의 특히 복귀 주소의 사용을 위해 활성 레코드를 사용한다.
꼬리 순환 : 순환 호출이 함수 끝에서 이루어지는 순환

• 장점 : 코드 짜기가 쉽고, 이해하기에도 명확하다.
• 단점 :
  1. 반복문에 비해 공간 복잡도가 높다. why? 반복문에서는 필요 없는 복귀 주소를 순환에서는 필요로 하기 때문.
  2. 반복문에 비해 속도가 느리다. why? 함수가 자기 자신을 호출하고 다시 되돌아가는 과정이 있기 때문.

사실 순환은 정의나 특징보다는 알고리즘 그 자체가 중요하기 때문에 간단한 알고리즘만 적고 튀튀하겠다.

팩토리얼 알고리즘

int factorial (int n)
{
    if ( n <= 1)
        return 1;
    return n * factorial(n-1); //여기서 순환 호출을 나중에 하는 것이 중요하다.
}

거듭제곱 알고리즘

int power (int x, int n)
{
    if (n == 0)
        return 1;
    else if (n%2 == 0)
        return power(x*x, n/2);
    else
        return x * power(x*x, (n-1)/2);
}

피보나치 수열 알고리즘

int fib (int n)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    
    return fib(n-1) + fib(n-2)
}