Recursive Thinking - 순환적으로 사고하기

• recursion은 프로그래밍적인 관점중 하나이다.
• recursion은 base case와 recursive case로 구성된다.
• base case란 종료지점 (메소드, 목적이 끝나는 지점을 말한다.)
• recursive case는 반복지점(목적을 이루기 위해 하는 행위)
• 여기서 중요한 것은 recursive case는 base case로 수렴해야한다.(발산을 하면 무한루프에 빠지므로 메소드가 끝나지 않는다.)
• 그럼 recursive case가 base케이스로 수렴을 할려면 어떻게 자기자신을 호출해야하는가?
• 아래 예제들을 살펴보면 종료지점을 정해 놓고 한개씩 값을 줄이면서 단계적으로 자기자신을 호출하고 있다.
• 여기서 중요한 것은 단계적이란 말이다.
• Recursive Thinking이란 것은 큰 문제가 발생하였을때 단계적으로 일을 쪼개서 처리하는 프로그래밍의 근본적인 사고를 말하는게 아닐까?

Recursion은 수학함수 계산에만 유용한가?

• 수학함수뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다.
• 반복문을 사용하는 모든 상황을 recursion으로 해결할 수 있다.

문자열의 길이 계산

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

• length(“ace”) <- return 1 + length(“ce”) <- return 1 + length(“e”) <- return 1+ length(“”) <- 0

문자열의 프린트

    public static void printChars(String str) {
  		if (str.length() == 0) {            // 이 함수의 base case
  			return ;
  		} else {                            // 이 함수의 recursive case
  			System.out.print(str.charAt(0));
  			printChars(str.substring(1));
  		}
  	}

문자열을 뒤집어 프린트

• “apple” 이라는 문자열이 있다. 이 문자열을 뒤집어서 출력을 할려면
  1. “a”를 제외한 “pple”을 뒤집어 프린트 한 후
  2. 마지막으로 “a”를 프린트하면 된다.

    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 static void printInBinary(int n) {
    if( n < 2) {
      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];
    }
  }
  

Recursion vs. Iteration

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