재귀함수(Recursive Method)

jihye lim·2019년 10월 22일

순차탐색 알고리즘 이진탐색 재귀함수

algorithm

목록 보기

1/1

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

재귀함수란 자기 자신을 호출하는 함수. but, 항상 무한루프에 빠지는 것은 아님.
recursive method의 기본 구성
→ base case : 재귀 호출에서 빠져나가기 위한 경우
ex) if(n<1) { return 0 }
→ recursive case : 자신을 호출하는 함수를 포함하는 경우
ex) else { myself(n-1) }
recursive를 사용하여 풀 수 있는 문제들

→ Factorial n!
```
  0! = 1
  n! = n * (n-1)! (if n>0)
```
→ X의 n승
```
  X의 0승 = 1
  X의 n승 = X*X의 n-1승 (if n>0)
```
→ Fibonacci Number(피보나치 수)
```
  F0 = 0
  F1 = 1
  Fn = Fn-1 + Fn-2 (if n>1)
```
→ Euclid Method 유클리드 호제법(최대공약수)

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

recursive thinking 순환적 사고
문자열의 길이 계산

if the string is empty
return 0;
else
return 1 plus the length of the string that excludes the first character;
```
  public static int length(String str) {
  	if (str.equals(""))
  		return 0;
  	else
  		return 1 + length(str.substring(1))
  }
```
str.substring(int startIndex) : str의 startIndex 문자부터 끝까지의 문자열을 리턴
str.substring(int startIndex, int endIndex) : str의 startIndex 문자부터 endIndex의 문자까지의 문자열을 리턴

문자열의 프린트

  public static void printChars(String str) {
  	if (str.length() == 0)
  		return;
  	else {
  		System.out.println(str.charAt(0));
  		printChars(str.substring(1));
  	}
  }

** str.charAt(int index) : index 위치의 문자 1개를 리턴

문자열을 뒤집어서 프린트

  public static void printCharsReverse(String str) {
  	if (str.length() == 0)
  		return;
  	else {
  		printCharsReverse(str.substring(1));
  		System.out.println(str.charAt(0));
  	}
  }

2진수로 변환하여 출력

  public 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으로 표현 가능함.
→ 순환함수는 복잡한 알고리즘을 단순하고 알기 쉽게 표현하는 것을 가능하게 함.
→ 하지만 함수 호출에 따른 오버헤드(overhead)가 있음(매개변수 전달, 액티베이션 프레임 생성 등)

Part 3. 순환적 알고리즘(Recursive Algorithm)의 설계

적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함.
모든 case는 결국 base case로 수렴해야 함.

암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꿔라.
- 순차 탐색(검색) sequential search
  : 정렬되어 있지 않은 배열 안의 어떤 값을 찾을 때 순서대로 하나씩 검사하는 알고리즘.
  
  → 이 함수의 미션은 data[0]부터 data[n-1] 사이에서 target을 검색한다. 하지만 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉 0은 '암시적 매개변수' 이다.
```
  int search(int[] data, int n, int target) {
  	for(i = 0; i < n; i++) {
  		if(data[i] == target) 
  			return i;
  	return -1;
  }
```
- 매개 변수의 명시화 : 순차 탐색
  → 이 함수의 미션은 data[begin]부터 data[end]사이에서 target을 검색한다. 즉, 검색구간의 시작점을 명시적(explicit)으로 지정한다.
```
  int search(int[] data, int begin, int end, int target) {
  	if(begin > end) 
  		return -1;
  	else if(target == data[begin]) {
  		return begin;
  	else
  		return search(data, begin+1, end, target);
  }
```
- 순차 탐색의 다른 버전
  → 중간에서 부터 앞 부분을 먼저 검색하고 그 안에서 target을 못 찾으면 뒷부분을 검색한다.
```
  int search(int[] data, int begin, int end, int target) {
  	if(begin > end) 
  	  return -1
    else {
  	  int middle = (begin+end)/2;
  		if(data[middle] == target) {
  			return middle;
  		int index = search(data, begin, middle-1, target);
  		if(index != -1) 
  			return index;
  		else
    		return search(data, middle+1, end, target);
  	}
  }
```
- 매개 변수의 명시화 : 최대값 구하기
  → 이 함수의 미션은 data[begin]과 data[end]사이에서 최대값을 찾아 반환하는 것이다. begin≤end라고 가정한다.
```
  int findMax(int[] data, int begin, int end) {
  	if (begin == end)
  		return data[begin];
  	else {
  		return Math.max(data, findMax(data, begin+1, end));
  }
```
- 최대값 찾기의 다른 버전
  → 배열을 중간으로 나눠 앞 부분의 최대값과 뒷부분의 최대값을 비교해서 최대값을 찾는 방법.
```
  int findMax(int[] data, int begin, int end) {
  	if (begin == end) 
  		return data[begin];
  	else {
  		int middle = (begin+end)/2;
  		int max1 = findMax(data, begin, middle);
  		int max2 = findMax(data, middle+1, end);
  		return Math.max(max1, max2);
```
- 이진 검색 binary search
  → 순차적으로 정렬된 배열의 시작과 끝 사이에서 어떤 값 a를 찾을 때, 그 배열의 중간의 값 m과 a를 비교하여
  a < m 라면 배열의 시작부터 m까지의 값 사이에 a가 있을 것이고
  a > m 라면 m부터 배열의 끝까지의 값 사이에 a가 있을 것임
```
  public static int binarySearch(String[] items, String target, int begin, int end) {
  	if(begin>end)
  		return -1;
  	else {
  		int middle = (begin+end)/2;
  		int compResult = target.compareTo(items[middle]);
  		if(compResult == 0) 
  			return middle;
  		else if(compResult > 0) 
  			return binarySearch(items, target, begin, middle-1);
  		else
  			return binarySearch(items, target, middle+1, end);
  	}
  }
```
  - string1.compareTo(string2)은
    string1 == string2일 때, 0을 리턴
    string1 > string2일 때, 1을 리턴
    string1 < string2일 때, -1을 리턴
    
    이 포스트는 인프런의 알고리즘 강좌 '권오흠님의 영리한 프로그래밍을 위한 알고리즘' 를 정리한 내용입니다.

jihye lim

iOS와 Java를 공부하는 개발자

재귀함수(Recursive Method)

algorithm

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

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

Part 3. 순환적 알고리즘(Recursive Algorithm)의 설계

0개의 댓글