2. 순환(Recursion)의 개념과 기본 예제2

2. 순환(Recursion)의 개념과 기본 예제2

 

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

반복문을 사용하여 짤 수 있는 프로그램을 재귀함수를 이용하여 작성할 수 있다.

​

예제)

문자열의 길이 계산

:라이브러리 함수 사용 가능 > 라이브러리 함수는 어떻게 문자열의 길이를 계산할까?

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

2진수로 변환하여 출력

public void printBinary (int n){
   if(n<2)
      system.out.print(n);
   else {
      printBinary(n/2); //n을 2로 나눈 몫을 먼저 2진수로 변환하여 인쇄한 후
      system.out.print(n%2); //n을 2로 나눈 나머지를 인쇄한다.
   }
}

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

Scanner in이 참조하는 파일로 부터 n개의 정수를 입력받아 배열 data의 data[0],…,data[n-1]에 저장한다.

* 자주 사용하는 방식은 아님.

public void readFrom(int n, int [] data, Scanner in) {
   if (n ==0)
     return;
   else {
      readFrom(n-1, data, in);
      data[n-1] = in.nextInt();
   }
}

Recursion vs Interation (순환 vs 반복)

1. 모든 순환함수는 반복문으로 변경가능하다.

그 역도 성립함. 즉, 모든 반복문은 Recursion으로 표현 가능하다.

2. 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다.

하지만, 함수 호출에 따른 오버헤드가 있다. = 속도에 약점을 갖는다.

 

<영리한 프로그래밍을 위한 알고리즘 강좌 - 권오흠 교수님>

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C#description

​