회고 18일차

이제는 알고리즘 중 재귀에 대해 알아보려고 한다.

 

재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴. 라는 뜻으로 쭉 안으로 들어갔다가 다시 원래 자리로 돌아온다는 느낌을 받으면 된다.

public void recursion() {
  System.out.println("recursion!");
  recursion();
}

계속 적 으로 자신을 호출하여 재귀를 하는 것을 재귀라고 합니다.

 

재귀라는 것은 문제를 가장 작은 단위로 쪼개서 해결하는 문제입니다.

만약 1+2+3+4+5라면

답은 : 5+f(4+3+2+1)이 될 것이고, 5+4+f(3+2+1) 이렇게 점점 내려갔다가 답을 끌고 올라와 정답이 될 것입니다.

사실 재귀는 for문으로 모두 구현이 가능합니다.  재귀는 어떤 경우 사용하냐면

1. 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

2. 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우

3. 볍수 사용을 줄여서 프로그램 오류가  발생할 가능성을 줄이는 경우 사용합니다.

 

코드를 통해 알아보겠습니다.

  public static String stringify(Object data) {

    // 이 메서드는 만약 사용자가 data를 넘겨줬을때, 그 데이터가  입력된 값이 문자열일 경우를 의미합니다.
    if (data instanceof String) {
      return getStringType(data);
    }

    if (data instanceof Boolean) {
      return getBooleanType(data);
    }
    if (data instanceof Integer) {
      return getIntType(data);
    }

    //입력된 값이 Object[]일 경우
    //이 부분이 배열이 들어왔을 경우를 의미합니다.
    if(data instanceof  Object[]){
      return String.format("[%s]",geteObject(data));
    }
    return null;
    }

private static String geteObject(Object data) {
  System.out.println(data.toString());
  if(((Object[])data).length==0)return "";
  if(((Object[])data).length==1)return stringify(((Object[]) data)[0]);
  Object[] data2 = Arrays.copyOfRange((Object[])data,1,((Object[]) data).length);
  Object[] end = Arrays.copyOfRange((Object[])data,0,1);
  return geteObject(end)+","+geteObject(data2);

}

다음은 java문법인 MAP, OBJECT, 모든 타입을 JSON 형식으로 만들기위해 모든 요소를 ""로 만들어 주는 코드입니다.

이 기능은 ObjectMspper의 writeValueAsString()을 통해 구현이 가능하지만, 한번 이해를 위해 손수 코딩을 해보았습니다.

 

이 요소에서 재귀를 찾으면 우선 가장 작은 범위인 String이 들어왔을 때 int 가 들어왔을 때 Boolean이 들어왔을 때 먼저 처리를 해준 상태에서 만약 큰 범위인 객체가 들어왔다면, 원소를 계속 작게 쪼개 첫번째원소와 그나머지로 구분하여 , 

가장 작은 원소는 재귀를 통해 원래 작성했던 Type 변환에 맞춰서 return이 되게됩니다. 가장 큰 객체를 점점 쪼개서 작은 범위로 만들고 그 값을 하나로 합치는 것이 재귀입니다.