재귀함수(Recursive Method)

jihye lim·2019년 10월 22일
0

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로 수렴해야 함.
  1. 암시적(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을 리턴

        이 포스트는 인프런의 알고리즘 강좌 '권오흠님의 영리한 프로그래밍을 위한 알고리즘' 를 정리한 내용입니다.

profile
iOS와 Java를 공부하는 개발자

0개의 댓글