재귀함수(Recursive Method)

jyebe·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!

    → X의 n승

    → Fibonacci Number(피보나치 수)

    → 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;

    str.substring(int startIndex) : str의 startIndex 문자부터 끝까지의 문자열을 리턴
    str.substring(int startIndex, int endIndex) : str의 startIndex 문자부터 endIndex의 문자까지의 문자열을 리턴

  • 문자열의 프린트

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

  • 문자열을 뒤집어서 프린트

  • 2진수로 변환하여 출력

  • 배열의 합 구하기

  • 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은 '암시적 매개변수' 이다.

    • 매개 변수의 명시화 : 순차 탐색
      → 이 함수의 미션은 data[begin]부터 data[end]사이에서 target을 검색한다. 즉, 검색구간의 시작점을 명시적(explicit)으로 지정한다.

    • 순차 탐색의 다른 버전
      → 중간에서 부터 앞 부분을 먼저 검색하고 그 안에서 target을 못 찾으면 뒷부분을 검색한다.

    • 매개 변수의 명시화 : 최대값 구하기
      → 이 함수의 미션은 data[begin]과 data[end]사이에서 최대값을 찾아 반환하는 것이다. begin≤end라고 가정한다.

    • 최대값 찾기의 다른 버전
      → 배열을 중간으로 나눠 앞 부분의 최대값과 뒷부분의 최대값을 비교해서 최대값을 찾는 방법.

    • 이진 검색 binary search
      → 순차적으로 정렬된 배열의 시작과 끝 사이에서 어떤 값 a를 찾을 때, 그 배열의 중간의 값 m과 a를 비교하여
      a < m 라면 배열의 시작부터 m까지의 값 사이에 a가 있을 것이고
      a > m 라면 m부터 배열의 끝까지의 값 사이에 a가 있을 것임

      • string1.compareTo(string2)은
        string1 == string2일 때, 0을 리턴
        string1 > string2일 때, 1을 리턴
        string1 < string2일 때, -1을 리턴

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

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

0개의 댓글