7. Recursion -2 (Java)

Goal

 - Recursive Thing : 순환적으로 사고하는법 알기

 - Recursion의 다양한 예제 공부

 - Recursion과 Iteration의 특징 및 차이점 알기.

1. Recursive Thinking 

 - 순환적으로 사고하기

 - Recursion을 사용하여 수학함수뿐 아니라 다른 많은 문제를 해결할 수 있다. (ex for문 while문 같은 반복문을 대신하여 사용할 수 있다)

 - 순환적 사고: 1 + (n-1) 형식이 주를 이루며 만약 n = 4일 경우 n = 4의 실행은 가장 나중으로 미루고(n=3 함수 불러오기 / n=4의 값 실행의 형태) n=3, n=2, n=1,, 까지 함수를 불러와 더이상 불러올 함수가 없는 상태부터 값을 계산한다  (즉, 실행은 순차적으로 미루고 맨 밑에서의 n=0값 부터 최종적으로 n-1까지 계산 할 수 있도록 함)

 

1-1 문자열의 길이 계산

 

1) 설명

 - recursion을 이용해서 입력받은 문자열의 길이를 계산.

 - 입력받은 문자열의 길이 : 1 + (총 문자열의 길이 - 1)

2) 자바 구현

 - str.substring(num) : num으로 입력한 개수만큼 문자열의 앞에서부터 문자를 잘라내고 나머지 문자들로 새로운 문자열을 만든다. 

 * str.substring(num) : 문자열 str에서 숫자의 개수(num)만큼 앞에서부터 문자를 잘라내고 나머지를 반환 

 ex) str = "abc"; str.substring(2) = return "c";

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

 

3) 동작 방식 

 

1-2 문자열의 프린트

  public static void printChars(String str) {
    if (str.length() == 0)
      return;
    else {
      System.out.print(str.charAt(0)); //charAt(index) 문자열의 index에 해당하는 문자를 return.
      printChars(str.substring(1));
    }
  }

 

1-3 문자열 뒤집어 프린트

 - 함수를 불러오는 것을 우선하여 문자열의 앞단을 하나씩 지우고, 최종적으로 str.length() == 0 값 부터 실행. 

 - 따라서 문자열이 뒤집어진 상태로 출력된다.

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

 

1-4 2진수로 변환하여 출력

 - 2진수에서 마지막 자리가 0이면 짝수 1이면 홀수

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

 

1-5 배열의 합 구하기

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

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

 

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

  public void readFrom(int n, int[] data, Scanner in) { // Scanner in : data 파일을 참조. 
    if (n == 0)
      return;
    else {
      readFrom(n-1, data, in);
      data[n-1] = in.nextInt();
    }
  }

 

2. Recursion vs Iteration

 - 모든 순환함수는 반복문(iteration)으로 변경 가능

 - 그 역도 성립함. 즉, 모든 반복문은 recursion으로 표현 가능함. 하지만 함수 호출에 따른 오버헤드가 있음 (매개변수 전달, 엑티베이션 프레임 생성 등)

 

 

* 더 알아보기

 - println vs print 

  - > System.out.println() 은 데이터를 출력한 후 자동으로 다음줄로 넘어감. 즉 "개행문자(줄바꿈 문자)"가 붙음. 엔터키(Enter Key)가 자동으로 쳐지는 효과. 반면 System.out.print() 는 줄바꿈을 하지 않음. 대부분의 경우 println() 을 쓰고, 줄바꿈을 하지 말아야 하는 특수한 경우에만 print() 를 사용.

 - Java 코드작성 스타일