Recursion

• 프로그램에서 어떤 함수가 자기 자신을 다시 호출하는 것

  • base case : 직접 함수값을 계산할 수 있는 경우
    • 입력값이 base case에 해당하는지 가장 먼저 검사하고 처리
    • 적어도 한 개 이상의 base case가 있어야 함
  • recursive step : base case가 만들어 질 때까지 계속 자신을 재귀호출해 나가면서 계산하는 과정
    • 적절한 base case가 없으면 무한 loop (stack overflow) 발생

• 분할정복, 동적계획법, 되추적기법 등에 사용됨

Types

• Unary recursion
  • 각 재귀마다 한 번씩의 재귀적 호출 수행
    • factorial, linear sum, reversing array
• Binary recursion
  • 각 재귀마다 두 번씩의 재귀적 호출 수행
    • fibonacci numbers, hanoi tower, merge sorting, quick sorting
• Multiple recursion
  • 각 재귀에 대해 세 번 이상의 재귀 호출
    • flood fill, knight’s tour

Function call stack

• 실행중인 함수가 지역변수 등 자신이 가지고 있는 정보를 저장할 공간
• 새로운 함수 수행이 완료된 후 다시 원래 호출했던 함수로 제어가 돌아올 때, 해당 함수에서 사용하던 정보를 복원해서 사용해야 함.
• 원래 함수로 되돌아 왔을 때 수행해야 할 프로그램의 주소(반환주소)도 저장해야 함

Activation Record

• 현재함수가 가지고 있던 정보를 저장하는 연속적인 메모리 공간

Call Stack

• activation record를 관리하는 공간

Call Stack Overflow

• 너무 많은 재귀 함수의 호출로 인해 call stack에 더 이상 저장할 공간이 없는 경우

Fibonacci

int fibo(int num) {
    if (num <= 1) {
        return num; 
    }

    return fibo(num-1) + fibo(num-2);
}

Reversing Array

void reverseArray(char s[], int start, int end) {
    if (start >= end) {
        return;
    }

    swap(s + start, s + end);

    reverseArray(s, start + 1, end - 1);
}

Factorial

• 마지막 0을 제외하고 3자리 수를 출력

long long factorial(long long a) {
    if (a <= 1) {
        return 1;
    }

    long long result = a * factorial(a - 1);

    while (result % 10 == 0) {
        result /= 10;
    }

    result %= 10000;

    return result;
}

Computing Powers

double power(double x, int n) {
    if (n == 0) {
        return 1.0;
    }
    else {
        return fmod(x * power(x, n-1), 1000.0);
    }
}

• n번의 재귀 호출

Fast Computing Powers

• x의 n승을 빠르게 구하는 알고리즘
  • 종료 조건 : 지수가 0인 경우, 1을 반환한다.
  • 지수가 홀수인 경우
    • y : x의 (n-1)/2승
    • y * y : x의 n-1승
    • x y y : x의 n승
  • 지수가 짝수인 경우
    • y : x의 n/2승
    • y * y : x의 n승

double power(double x, int n) {
    double y;

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

• log(n)번 재귀 호출

Greatest Common Divisor

• 유클리드 호제법

int euclid(int a, int b) {
    int r;

    if (b == 0) {
        return a;
    }

    r = a % b;
    return euclid(b, r);

}