흔히 볼 수 있는 자바 면접 문제(4): 교체(iteration)와 귀속(recursion)

자세히 보기
Q. 주어진 텍스트 내 문자 "A"의 개수를 계산하는 코드를 쓰십시오.각각 교체와 귀속 두 가지 방식을 사용한다.
A. 주어진 텍스트가 "AAA rating"이라고 가정합니다.교체 방식은 다음과 같이 매우 직관적이다.

public class Iteration {

    public int countA(String input) {
        if (input == null || input.length( ) == 0) {
            return 0;
        }

        int count = 0;
        for (int i = 0; i < input.length( ); i++) {
            if(input.substring(i, i+1).equals("A")){
                count++;
            }
        }
        return count;
    }

    public static void main(String[ ] args) {
          System.out.println(new Iteration( ).countA("AAA rating"));     // Ans.3
    }
}

 
다음은 다음과 같은 반복 코드입니다.

public class RecursiveCall {

    public int countA(String input) {

        // exit condition – recursive calls must have an exit condition
        if (input == null || input.length( ) == 0) {
            return 0;
        }

        int count = 0;

        //check first character of the input
        if (input.substring(0, 1).equals("A")) {
            count = 1;
        }

        //recursive call to evaluate rest of the input
        //(i.e.  2nd character onwards)
        return count + countA(input.substring(1));
    }

    public static void main(String[ ] args) {
        System.out.println(new RecursiveCall( ).countA("AAA rating"));	// Ans. 3
    }
}

 
귀속은 비교적 이해하기 어려우니, 우리는 아래의 그림으로 설명한다.
Q. 귀속을 이해하려면 어떤 개념을 알아야 하나요?
A. 리셋 방법(re-entrant method)은 안전하게 들어갈 수 있는 방법이다. 같은 방법이 실행되고 있어도 같은 라인의 호출 창고에 깊이 들어가도 이번 실행의 안전성에 영향을 주지 않는다.다시 들어갈 수 없는 방법은 안전하게 들어갈 수 있는 것이 아니다.예를 들어 파일을 쓰거나 파일에 로그를 쓰는 방법이 다시 들어갈 수 있는 방법이 아닐 때 그 파일을 망가뜨릴 수 있습니다.
만약 한 방법이 그 자신을 호출했다면, 우리는 귀속 호출이라고 부른다.창고 공간이 충분하다고 가정하면 귀속 호출은 디버깅하기 어렵지만 자바 언어에서 귀속 호출을 실현하는 것도 충분히 가능하다.귀속 방법은 많은 알고리즘 중에서 순환을 대체하는 좋은 선택이다.모든 귀환 방법은 다시 들어갈 수 있지만, 모든 귀환 방법은 귀환하는 것이 아니다.
창고는 LIFO(Last In First Out) 규칙을 준수하기 때문에 귀속 호출 방법은'호출자'를 기억하고 이 실행이 끝난 후에 당초 호출된 위치로 되돌아오는 것을 알 수 있습니다.시스템 창고를 이용하여 방법이 호출한 반환 주소를 저장합니다.Java는 스택 기반 프로그래밍 언어입니다.
이 사고방식에 따라 면접을 볼 수 있는 질문도 있습니까?
Q. 어떤 경우에 귀속을 해야 하나요?
A. 위의 예에서 귀속 방식을 사용할 필요가 없습니다. 순환 방식은 목적을 달성할 수 있지만 일부 상황에서 귀속 방식을 사용하면 코드가 더욱 간단하고 읽기 쉽습니다.귀속 방법은 순환 트리 구조와 추악한 끼워 넣는 순환을 피하는 데 매우 좋다.
Q. 미귀환이란 무엇인가, 왜 미귀환이 필요한가?위의 코드는 꼬리 귀속 방식으로 어떻게 다시 씁니까?
A. 일반적인 귀속 방법(또는 헤드 귀속)은 위에서 설명하였는데, 이런 방식은 호출 창고의 크기를 증가시킬 수 있다.매번 귀속할 때마다 입구는 창고에 기록되어야 한다.방법이 되돌아오기 전에counta(input.substring(1)의 결과에 count를 추가해야 합니다.count가 1보다 크다고 가정하면 반환 결과는count+counta(input.substring(1))입니다. 물론 사전에 counta(input.substring(1)를 계산해야 합니다.또한 이것은counta(input.substring(1)가 계산될 때까지 최종 결과를 얻을 수 있다는 것을 의미한다.따라서 마지막으로 해야 할 일은 사실 가산 연산이지 귀속 자체가 아니다.
귀착의 장점은 무엇입니까?
미귀환에서 마지막으로 해야 할 일은 귀환이다. 가산 연산은 이전에 이미 완성되었다.한 차례의 귀속 조정이 끝난 후에는 다른 일이 없기 때문에 호출할 때 생성된 정보도 아무 소용이 없다.이런 쓸모없는 정보는 버리고 새로운 매개 변수로 귀속 방법을 호출하여 새로운 결과를 만들 수 있다.창고 호출 감소는 메모리 소모 감소를 가져오고 프로그램의 성능이 더 좋다는 것이다.
다시 쓰는 코드는 다음과 같습니다.

public class TailRecursiveCall {

 public int countA(String input) {

  // exit condition – recursive calls must have an exit condition
  if (input == null || input.length() == 0) {
   return 0;
  }

  return countA(input, 0) ;
 }

 public int countA(String input, int count) {
  if (input.length() == 0) {
   return count;
  }

  // check first character of the input
  if (input.substring(0, 1).equals("A")) {
   count = count + 1;
  }

  // recursive call is the last call as the count is cumulative
  return countA(input.substring(1), count);
 }

 public static void main(String[] args) {
  System.out.println(new TailRecursiveCall().countA("AAA rating"));
 }
}