끄적끄적 개발 블로그입니다.

3 분 소요

재귀 호출

재귀란(recursion)?

어떠한 것을 정의할 때 자기 자신을 참조하는 것

재귀 함수(Recursion Function)란?

함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식

  • 반복과 재귀는 유사한 작업을 수행할 수 있다.

  • 반복은 수행하는 작업이 완료될 때까지 계속 반복
    • 루프(for/while, do~while 구조)
  • 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법
    • 하나의 큰 문제를 해결할 수 있는(해결하기 쉬운) 더 작은 문제로 쪼개고 결과들을 결합한다.
    • 재귀함수로 구현

재귀 함수recursive function

  • 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수.

  • 일반적으로 재귀적 정의를 이용해서 재귀 함수를 구현한다.

    ➡따라서, 기본 부분(basis part)와 유도 부분(inductive part)로 구성된다.

  • 재귀적 프로그램을 작서하는 것은 반복 구조에 비해 간결하고 이해하기 쉽다.

  • 함수 호출은 프로그램 메모리 구조에서 스택을 사용한다.

    ➡ 재귀 호출은 반복적인 스택의 사용을 의미하며 메모리 및 속도에서 성능 저하가 발생한다.

백토리얼 재귀 함수

  • 재귀적 정의

    Basis rule:
	N<= 1 경우, n=1
Inductive rule:
	N >1, n! = n * (n-1)!
    • Inductive: 귀납적인, 유도적인

  • n!에 대한 재귀함수

    int fact(int n)
{
    if(n <= 1)	//Basis part
        return 1;
    else		//Inductive part
        return n*fact(n-1);
}

[1차원 배열의 모든 원소 출력을 재귀로 작성]

static int arr[] = {10, 20, 30};

private static void printArray1() {
    for(int i=0; i<arr.length; ++i){
        System.out.print(arr[i]+"\t");
    }
    System.out.println();
}

image-20240620094808273

유도파트: 반복적으로 실행

  • 해결할 문제을 고려해서 반복이나 재귀의 방법을 선택

  • 재귀는 문제 해결을 위한 알고리즘 설계가 간단하고 자연스럽다.

    • 추상 자료형(List, tree등)의 알고리즘은 재귀적 구현이 간단하고 자연스러운 경우가 많다.

  • 일반적으로, 재귀적 알고리즘은 반복(lterative) 알고리즘보다 더 많은 메모리와 연산을 필요로 한다.

  • 입력 값 n이 커질 수록 재귀 알고리즘은 반복에 비해 비효율적일 수 있다.

      재귀 반복
    종료 재귀 함수 호출이 종료되는 베이스 케이스(base case) 반복문의 종료 조건
    수행시간 (상대적) 느림 빠름
    메모리 공간 (상대적) 많이 사용 적게 사ㅛㅇ
    소스 코드의 길이 짧고 간결 길다
    소스 코드 형태 선택 구조(if..else) 반복 구조(for, while)
    무한 반복시 스택 오버플로우 CPU를 반복해서 점유

피보나치

  • 이전의 두 수 합을 다음 항으로 하는 수열을 피보나치라 한다.

    0, 1, 1, 2, 3, 5, 8, 13,...

  • 피보나치 수열의 i번 째 값을 계산하는 함수 F를 정의 하면 다음과 같다.

    F0=0, F1=1

    Fi=Fi-1+Fi-2for i>=2

  • 위의 정의로부터 피보나치 수열의 i번째 항을 반환하는 함수를 재귀함수로 구현할 수 있다.

  • 피보나치 수를 구하는 재귀함수

    image-20240620102856347

완전 검색 baby-gin

0~9 사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때, 3장의 카드가 연속적인 번호를 갖는 경우를 run이라 하고, 3장의 카드가 동일한 번호를 갖는 경우를 triplet이라고 한다.

그리고, 6장의 카드가 run과 triplet로만 구성된 경우를 baby-gin으로 부른다.

6자리의 숫자를 이력 받아 baby-gin 여부를 판단하는 프로그램을 작성하라

  • 667767

    667767은 두 개의 triplet이므로 baby-gin이다(666,777)

  • 054060

    054060은 한 개의 run과 한 개의 triplet이므로 역시 baby-gin이다(456,000)

  • 101123

    101123은 한 개의 triplet가 존재하나, 023이 run이 아니므로 bavy-gin이 아니다.

    123을 run으로 사용하더라도 011이 run이나 triplet가 아님

  • 입력 받은 숫자를 정렬한 후, 앞뒤 3자리씩 끊어서 run 및 triplet을 확인하는 방법을 고려할 수도 있다.

    • {6,4, 4, 5, 4, 4}

      ✔ 정렬하여{4, 4, 4, 4, 5, 6}을 얻어내면 쉽게 baby-gin을 확인할 수 있다.

    • {1, 2, 3, 1, 2, 3}

      ✔ 정렬하면 {1, 1, 2, 2, 3, 3}로서, 오히려 baby-gin 확인을 실패할 수 있다.

  • 위의 예처럼, 탐욕 알고리즘적인 접근은 해답을 찾아내지 못하는 경우도 있으니 유의해야한다.

  • 완전 검색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 학인하는 기법이다.
  • Brute-force 혹은 generate-and-test 기번이라고도 불리 운다.
    • “Just-do-it”
    • force의 의미는 사람(지능)보다 컴퓨터의 force를 의미한다.
  • 모든 경우의 수를 테스트한 후, 최종 해법을 도출한다.
  • 상대적으로 빠른 시간에 문제 해결(알고리즘 설계)을 할 수 있다.

  • 일반적으로 경우의 수가 상대적으로 작을 때 유용하다.

  • 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 작다.

  • 검정 등에서 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직 하다.

  • 고려할 수 있는 모든 경우의 수 생성하기

  • 해답 테스트 하기

  • 고려할 수 있는 모든 경우의 수 생성하기

    • 6개의 숫자로 만들 수 있는 모든 숫자 나열(중복 포함)

      ex)입력으로 {2, 3, 5, 7, 7, 7}을 받았을 경우, 아래와 같이 순열을 생성 가능

      image-20240620155354362

  • 해답 테스트하기

    • 앞의 3자리와 뒤의 3자리를 잘라, run와 triplet 여부를 테스트하고 최종적으로baby-gin을 판단한다.

      image-20240620155457821

완전 검색

많은 종류의 문제들이 특정 조건을 만족하는 경우나 요소를 찾는 것이다.

또한, 이들은 전형적으로 순열(permutation), 조합(combination), 그리고 부분집합(subset)과 같은 조합적 문제들(Combinational Problems)과 연관된다.

반복문

for문의 용도

  • 규칙적인 반복

    0부터 2까지 출력

  • 일정횟수 반족

➡ for문 사용

업데이트:

댓글남기기

참고