알고리즘 study -11-

<재귀함수 디자인 예제>

---

• n^m을 재귀함수를 이용하여 계산하라

1. getPower(n, m) = n^m 을 반환하는 함수 // 말로 정의
2. getPower(n, 0) = 1 // 기저 조건(해보나 마나 뻔한 것들)
3. getPower(n, m) = getPower(n, m-1) * n // 가정 후 수학적 귀납법을 통해 가정이 맞는지 확인

#include <stdio.h>

//함수 마다 어떤 기능을 하는지 설명 적어두는 습관!

int getPower(int n, int m){
  // n^m 을 구하는 재귀함수
  
  // 기저 조건
  if(m == 0)
    return 1; // 0승은
  else
    return getPower(n, m-1) * n;
}


int main() {

  int n, m;
  
  scanf("%d %d", &n, &m);
  
  printf("%d\n", getPower(n,m));

  return 0;
}

---

- N 부터 M까지의 합 구하기

1. getSum(n,m) => n 부터 m까지의 합을 구하는 함수
2. getSum(n,n) = n
3. getSum(n,m) = getSum(n, m-1) + m

#include <stdio.h>

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

int main() {

  int n, m;
  scanf("%d %d", &n, &m);
  
  printf("%d\n", getSum(n,m));

  return 0;
}

---

- 각 자릿수의 합

1. getDigitSum(x) : x의 각 자릿수의 합을 반환하는 함수
2. getDigitSum(x) = x : x가 한자리 수 일 경우
3. getDigitSum(x) = getDigitSum(x/10) + (x % 10)

#include <stdio.h>


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

}

int main() {
  
  int x;
  scanf("%d", &x);
  
  printf("%d\n", getDigitSum(x));

  return 0;
}

---

- 이진수 출력하기

1. printBinary(x) : x를 이진수로 바꾼 결과를 출력하는 함수
2. printBinary(1) = 1 / printBinary(0) = 0
3. printBinary(x) 출력 = printBinary(x/2) 출력 + (x % 2)출력

#include <stdio.h>


void printBinary(int x){
  if(x == 0){
    
  }
  else{
    printBinary(x/2);
    printf("%d", x%2);
  }
}

int main() {

  int x;
  scanf("%d", &x);
  
  printBinary(x);

  return 0;
}

---

- 펠린드롬인지 판별하기

-> 뒤집어도 똑같은 문자열

재귀적 패턴 -> 문자열 양끝을 제왼한 내부가 펠린드롬인 경우 현재 양끝 문자가 같으면 전체도 펠린드롬이다
ex> a(bcdcb)a

1. isPalindrome(myString, start, end) : myString(문자열)의 start 부터 end 까지 palindrome이면 true, 아니면 false를 반환하는 함수
2. isPalindrome(myString, idx, idx) = true

#include <string.h>

bool isPalindrome(char myString[], int start, int end){
  // myString의 start-end가 펠린드롬이면 true,
  // 아니면 false를 반환하는 함수
  
  if(start >= end) // 이 상황까지왔으면 펠린드롬임
    return true;
  else{
    if(myString[start] == myString[end])
      return isPalindrome(myString, start+1, end-1);
    else
      return false;
  }
  
}

int main() {

  char myString[100];
  scanf("%s", myString);
  
  int len = strlen(myString);
  
  if(isPalindrome(myString, 0, len-1))
    printf("Yes\n");
  else
   printf("No\n");

  return 0;
}

---