알고리즘- 순환(recursion)의 개념과 예제 2

알고리즘- 순환(recursion)의 개념과 예제 2

이 내용은 인프런 영리한 프로그래밍을 위한 알고리즘 강좌를 참고한 내용입니다.

| 들어가기에 앞서,

Q) recursion은 수학함수 계산에만 유용한가?

A) 수학함수뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다.

| 문자열의 길이 계산

if the string is empty
    return 0;
else
  return 1 plus the length of the string that
    excludes the first character;

위의 설명은 코드로 설명하면 아래와 같다.

public static int length(String str){
  if(str.equals(""))
    return 0;
  else
    return 1+length(str.substring(1));
}

| 문자열의 프린트

위와 비슷하다.

public static void printChars(String str){
  if(str.equals(""))
    return ;
  else{
    System.out.print(str.charAt(0));
    printChars(str.substring(1));
  }
}

반대로 프린트하는 예는 아래와 같다.

public static void printChars(String str){
  if(str.equals(""))
    return ;
  else{
    printChars(str.substring(1));
    System.out.print(str.charAt(0));
  }
}

| 2진수로 변환하여 출력

public static void printInBinary(int n){
  if(n<2)
   System.out.print(n);
  else{
    printInBinary(n/2);
    System.out.print(n%2);
  }
}

음이 아닌 정수 n 을 이진수로 변환하여 프린트하는 예제이고, n을 2로 나눈 몪을 먼저 2진수로 변환하여 인쇄한 후 n을 2로 나눈 나머지를 인쇄한다.
|배열의 합 구하기

public static int sym(int n, int [] data){
  if(n<=0)
   return 0;
  else
    return sum(n-1, data) + data[n-1];
}

data[0]에서 data[n-1]까지의 합을 구하여 반환한다.
|데이터파일로 부터 n 개의 정수 읽어오기

public void readFrom(int n, int [] data, Scanner in){
  if(n==0)
   return;
  else{
    readFrom(n-1,data,in);
    data[n-1]=in.nextInt();
  }
}

scanner in이 참조하는 파일로 부터 n개의 정수를 입력받아 배열 data의 data[0]~ data[n-1] 에 저장한다.
| Recursion vs Iteration
- 모든 순환함수는 반복문(iteration)으로 변경 가능- 그역도 성립함. 즉 모든 반복문은 recursion으로 표현 가능함.- 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 함.- 하지만 함수 호출에 따른 오버헤드가 있음(매개변수 전달, 액티베이션 프레임 생성 등)