Recursive Call, Recursive Function   재귀 호출, 재귀 함수, 순환 함수

(2019-06-07)

재귀, 순환, Recursion, 재귀 프로그램

1. 재귀 함수 / 순환 함수 (Recursive Function) / 재귀 서브프로그램함수 정의에서, 
     - 자기 자신을 사용하여 정의함

  ㅇ 용도
     - 마치 루프처럼 어떤 일을 반복적으로 수행하는데에 유리함
     - 트리연결 리스트와 같은 컴퓨터 자료구조에 유용

  ㅇ 例) 
     - 피보나치 수열의 정의 : (직전 2개 항의 합으로 정의됨)
        .  fib(0) = 0; fib(1) = 1; fib(n) = fib(n-1) + fib(n-2), (n>2);
     - 팩토리얼의 정의 : (현재 항 및 직전 항의 곱으로 정의됨)
        .  factorial(1) = 1; result = factorial(n) * factorial(n-1);


2. 재귀 함수 특징루프(반복)와 달리 재귀는,
     - 메모리에 함수 복사본을 반복적으로 만들기 때문에,
     - 루프(반복) 보다 느리고 더 많은 메모리가 필요

  ㅇ 프로그램을 이해하기 쉽고, 간결하게 작성 가능

  ㅇ 내포 구조(nested)로 된 데이터를 다루기에 적합함
     - 재귀 호출시 함수코드도 데이터 처럼 내포된 구조로써 포함되는
     - 추상 자료형 형태로도 볼 수 있음


3. 재귀 함수 형태

  ㅇ ① 종료 조건 (base case)
     - 먼저, 재귀 호출의 종료 여부를 판단할 수 있도록 함
     - 충분히 작아진 문제에서, 직접 해결 (그 결과를 바로 윗선에 반환)

  ㅇ ② 재귀 호출 (recursive case)
     - 각 단계 마다, 종료 조건에 접근하도록 그 자신을 재귀적으로 호출
     - 원래 문제 보다 작아진 부문제를 대상으로 함

  ㅇ 한편, 
     - 재귀기법은 반복기법으로도 프로그래밍 구현이 가능            ☞ 반복문 참조
     - 다만, 재귀(순환)은, 반복 보다 훨씬 명확하고 간결하게 표현 가능
     - 결국, 프로그래밍 용이성 및 메모리 소요 크기로써 이 둘 (재귀/반복) 중에 선택 필요


[알고리즘] 1. 알고리즘 2. 알고리즘 설계 3. 계산 복잡도 4. 하노이 탑 5. 순서도 6. 재귀 호출
[알고리즘 종류]

 
        최근수정     요약목록     참고문헌