[개념 학습 및 정리] 재귀함수

1. 재귀함수

일반적으로 두 가지 계산 방법이 존재한다.

• 순차적 계산 방법
• 귀납적 계산 방법

 

순차적 계산 방법은 차례차례로 계산 하는 것으로 가장 기본적인 방법이다. 반면 귀납적 계산은 "나"를 계산하기 위해 또 다시 "나"를 활용하는 방법이다. 귀납적 방법은 수많은 가정을 하다 가장 마지막에는 정해진 규칙에 의해 정확한 값을 통해 성립하는 것을 확인한다.

5^4 = 5^3 x 5 // 5^3은 5를 세번 곱한다는 가정
5^3 = 5^2 x 5 // 5^2은 5를 두번 곱한다는 가정
5^2 = 5^1 x 5 // 5^1은 5를 한번 곱한다는 가정
5^1 = 5^0 x 5 // 5^0은 1이라는 규칙이 있기에 모든 과정이 성립

 

즉, 재귀함수는 자기 자신을 호출하여 계산하는 방식이다. 재귀함수 디자인은 3가지 절차로 진행된다.

• 함수의 역할을 말로 정확하게 정의
• 제일 단순한 경우에서 함수가 제대로 동작함을 확인
• 함수가 제대로 동작한다고 가정하고 함수 완성

 

 

 

2. 팩토리얼

재귀함수 디자인은 다음과 같다.

• getFactorial(n)은 n!을 반환하는 함수
• n = 1 일 경우 동작 확인
• getFactorial(n) = getFactorial(n-1)

 

int getFactorial(int n) {
  if(n == 0) return 1;
  else return n * getFactorial(n-1);
}

 

 

 

 

3. 거듭제곱

재귀함수 디자인은 다음과 같다.

• getPower(n, m)은 n^m을 반환하는 함수
• m = 0 일 경우 동작 확인
• getPower(n, m) = getPower(n, m-1) x n

 

int getPower(int n, int m) {
  if(m == 0) return 1;
  return getPower(n, m-1) * n;
}

 

 

 

 

4. N to M

N부터 M까지의 합을 구하는 재귀함수 디자인은 다음과 같다.

• getSum(n, m)은 n 부터 m까지의 합을 구하는 함수
• n = 1, m = 1일 경우 동작 확인
• getSum(n, m) = getSum(n, m-1) + m

 

int getSum(int n, int m) {
  if(n == m) return n;
  return getSum(n, m-1) + m;
}

 

 

 

5. 각 자릿수의 합

십진수 N을 입력받아 각 자릿수의 합을 구하는 재귀함수 디자인은 다음과 같다.

• getDigitSum(x)은 x의 각 자릿수의 합을 반환하는 함수
• x = 1 일 경우 동작 확인
• getDigitSum(x) = getDigitSum(x/10) + x%10

 

int getDigitSum(int x) {
  if(x >= 0 && x <= 9) return x;
  return getDigitSum(x/10) + x%10;
}

 

 

 

6. 이진수 출력

재귀함수 디자인은 다음과 같다.

• printBinary(x)는 x를 이진수로 바꾼 결과를 출력하는 함수
• x = 0, 1 일 경우 동작 확인
• printBinary(x) = printBinary(x/2); System.out.println(x%2);

 

void printBinary(int x) {
  if(x == 0) System.out.println("0");
  else if(x == 1) System.out.println("1");
  else {
    printBinary(x/2);
    System.out.println(x%2);
  }
}

 

 

 

7. 팰린드롬 판별

팰린드롬은 입력받은 문자열이 뒤집어도 동일한 문자열을 의미한다. 패턴과 재귀함수 디자인은 다음과 같다.

// 양 끝이 같고 그 내부가 팰린드롬이면 팰린드롬
a(bcdedcb)a

• isPalindrom(myString, start, end)는 start부터 end까지가 팰린드롬이면 true 아니면 false를 반환하는 함수
• myString이 알파벳이 하나이고 start == end 일 경우를 확인
• isPalindrom(myString, start, end) = isPalindrom(myString, start+1, end-1)

 

boolean isPalindrom(char myString[], int start, int end) {
  if(start == end) return true;
  else if(start+1 == end){
    if(myString[start] == myString[end]) return true;
    else return false;
  } else {
    if(myString[start] == myString[end]) return isPalindrom(myString, start+1, end-1);
    else return false;
  }
}

 

 

 

8. 완전 탐색

N개의 카드가 있고 각각은 1부터 N까지의 번호를 갖을 때, 한 줄로 세울 수 있는 모든 경우를 출력하는 문제는 코드를 작성하기 까다롭다. 재귀함수를 이용하지 않을 경우의 N중 for문 코드는 다음과 같다.

for(int i = 1; i <= n; i++) {
  for(int j = 1; j <= n; j++) {
    for(int j = 1; i <= n; i++) {
      ...
}

 

재귀함수 디자인은 다음과 같다.

• doRecursion(x)는 x 번째 for문을 실행하는 함수
• x = 0, 1 일 경우 동작 확인
• doRecursion(x)

 

void doRecursion(int current, int n, int result[]) {
  if(current >= n) print(result);
  else {
    for(int i = 1; i <= n; i++) {
      if(isNotContaining(result, i)) {
        result[current] = i;
        doRecursion(current+1, n, result);
        result[current] = 0;
      }
    }
  }
}

예를 들어 순열에 대한 함수는 다음과 같이 작성할 수 있다.

int n, r;
bool check[100];

void doRecursion(int x) {
  if(x >= n) print(result);
  else {
    for(int i = 0; i < n; i++) {
      char alpha = i + 'a';
      if(check[i] == false) {
        check[i] = true;
        doRecursion(x+1);
        check[i] = false;
        result[x] = 0;
      }
    }
  }
}

/*
n = 4, r = 3
abc
abd
acb
acd
adb
adc
bac
bad
...
*/