순환(Recursion)의 개념, 기본예제2

문자열의 길이 계산

일반적인 문자열 길이 계산

1. 첫번째 문자를 제외한다.
2. 첫번째 문자를 제외한 나머지 길이를 계산한다.
3. 나머지 길이에 1을 더한다.

Pseudo code

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; /* base case */
  else
    return 1+length(str.substring(1)); /* recursive case */
}

문자열의 프린트

public static void printChars(String str){	
  if(str.length()==0)
    return;
  else{
    System.out.print(str.charAt(0)); /* charAt() 문자열의 첫 문자를 리턴 */
    printChars(str.substring(1));
  }
}

문자열을 뒤집어 프린트

1. 한 문자열을 뒤집어 프린트하려면
2. 먼저 문자열을 뒤집어 프린트 한 후
3. 마지막으로 첫 글짜를 프린트 한다.

public static void printCharsReverse(String str){
  if(str.length()==0)
    return;
  else{
    printCharsReverse(str.substring(1));
    System.out.print(str.charAt(0));
  }
}

2진수로 변환하여 출력

음이 아닌 정수 n을 이진수로 변환하여 인쇄한다.

public void printInBinary(int n){
  if(n<2) /* base case */
    System.out.print(n);
  else {
    printInBinary(n/2); // n을 2로 나눈 몫을 먼저 2진수로 변환하여 인쇄한 후 
    System.out.print(n%2); // n을 2로 나눈 나머지를 인쇄한다.
  }
}

배열의 합 구하기

data[0]에서 data[n-1]까지의 합을 구하여 반환한다.

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

데이터파일로 부터 n개의 정수 읽어오기

Scanner in이 참조하는 파일로 부터 n개의 정수를 입력받아 배열 data의 data[0] ,..., data[n-1]에 저장한다.

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

Recursion vs. Iteration

• 모든 순환함수는 반복문(iteration)으로 변경 가능
• 그 역도 성립함. 즉 모든 반복문은 recursion으로 표현 가능함
• 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 함
• 하지만 함수 호출에 따른 오버헤드가 있음 (매개변수 전달, 액티베이션 프레임 생성 등)

Reference

• 인프런, "영리한 프로그래밍을 위한 알고리즘 강좌, 제1-2강 Recursion의 개념과 기본 예제들(2/3)", https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/lecture/4073(2020.04.21)