흔한 자바 면접문제: 교체(iteration)와 귀속(recursion)

출처: ImportNew
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"));
  }
 }