재귀함수 - 재귀적으로 작성하는 법

1. 재귀 카테고리 : 반복 실행

  - 반복적으로 한 작업을 실행하는 알고리즘이다.

  - 파라미터를 전달해 반복 계산한다.

  - 재귀에는 항상 종료 조건이 있어야 한다.(!)

  - 재귀 함수는 전체 작업의 일부만 수행하고, 나머지는 재귀 호출에 위임한다.

 

2. 재귀 카테고리 : 계산

  - 하위 문제의 계산 결과에 기반해 계산할 수 있다.

  - 하위 문제는 입력값을 더 작게 한 똑같은 문제이다.

  - Factorial 함수가 대표적이다.

  - 계산 방식은 "상향식"과 "하향식"이 있는데, 상향식은 루프와 재귀의 방식이 같다.

  - 하향식이야 말로 재귀를 사용하는 주된 이유이다.

 

3. 하향식 재귀 : 새로운 사고방식

  3-1. 하향식 사고 절차

    a. 작성 중인 함수를 이미 누군가 구현해 놓았다고 상상하자.

    b. 문제의 하위 문제를 찾자.

    c. 하위 문제에 함수를 호출하면 어떻게 되는지 보고 거기서부터 시작하자.

 

3-2. 문자열 뒤집기 함수 작성

    a. 함수는 "abcde" 라는 인수를 받으면 "edcba"를 반환하는 reverse 함수이다.

    b. 먼저 하위문제를 찾자. 'a'를 제외한 "bcde"라고 가정하자.

    c. 누군가가 이미 reverse()함수를 구현해 놓았다고 가정하자.

    d. 이미 reverse()가 동작하니 reverse("bcde")를 호출하면 return "edcb"가 온다.

    e. 그러면 마지막에 제외했던 'a'를 붙이면 된다.

    f. 마지막에 기저조건을 추가하자.

String reverse(string) {
    // 기저조건
    if (string.length == 1) return string[0];
    return reverse(string[1, string.length - 1]) + string[0];
}

 

  3-3. 계단 문제

    a. N개까지 계단이 있고 한번에 하나, 둘 혹은 세 계단까지 올라갈 수 있다. 계산 끝까지 올라가는 경로는 몇 개일까?

    b. 11개짜리 계단이면 하위 문제는 10개짜리 계단의 올라가는 경우의 수이다.

    c. 한번에 두계단, 세계단까지 올라갈 수 있으니 9개, 8개짜리 계단의 올라가는 경우의 수도 합해야 한다.

    d. return path(n-1) + path(n-2) + path(n-3)이다.

    e. 기저조건을 정하면 계단이 1개면 return 1이다.

    f. path(2)는 return path(1) + path(0) + path(-1)이므로 1 + x + 0, 즉, path(0)의 return 1이 되어야 한다.

int path(int n) {
    if (n < 0) return 0;
    if (n == 1 || n == 0) return 1;
    return path(n-1) + path(n-2) + path(n-3);
}