재귀 호출 ( Recursive call )

1. 개요

[그림 1] 재귀호출의 과정

 재귀적 호출 함수 ( Recursive call ) 란 작업을 작은 단위로 쪼개서 재귀 호출된 함수 내에서 이 조각중에 하나를 해결하고, 나머지 조각들은 자기 자신을 또 호출해서 해결하는 방식으로 처리되는 함수로 간단히 말해서 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수이다.

재귀호출함수를 구현하려면 2가지 부분이 필요하다. 하나는 기본 부분 (Base part)와 유도 부분 (Inductive part)이다. 기본 부분은 재귀호출이 나중엔 결국 끝이 나야하므로 종결조건을 위한 부분이고 유도 부분은 새로운 집합의 원소를 생성하기 위해 재귀하는 부분이다.

재귀적 프로그래밍은 일반 반복 ( for,,while...등 ) 프로그래밍에 비해 간결하다는 점이 있지만, 재귀호출 특성상 반복적으로 스택을 사용하므로 메모리 및 속도에서 성능저하가 발생할 수도 있으며, 특정 시점에서 재귀적호출을 종료하지 못하면 ( 기본부분이 제대로 구현되지 않는 경우) 무한 재귀호출에 빠질 수 있다는 점이 있다.

	재귀	반복
종료	재귀함수 호출이 종료되는 기본 부분(Base part)가 필요	반복문이 종료 조건
수행 시간	반복에 비해 느림	빠름
메모리 공간	반복에 비해 많이 사용	적게 사용
소스 코드 길이	짧고 간결	길다
소스 코드 형태	선택 구조 (if ~ else)	반복 구조 (for, while, do while)
무한 반복 시	Stack Overflow 발생	CPU 반복점 점유

                

[표 1] 재귀와 반복의 차이점

---

2. 재귀호출을 이용한 여러가지 예.. ( Power, Sort.... )

[그림 2] 2의 N승 구하기 재귀호출 과정

#include <stdio.h> int iteratorPowerOf2(int power); int recursivePowerOf2(int power); int main() { int power = 4; printf("2의 %d승의 값 = %d\n", power, iteratorPowerOf2(power)); printf("2의 %d승의 값 = %d\n", power, recursivePowerOf2(power)); return 0; } int iteratorPowerOf2(int power) { int sum = 1; for (int i = 0; i < power; i++) { sum = sum * 2; } return sum; } int recursivePowerOf2(int power) { if (power < 1) return 1; return 2 * recursivePowerOf2(--power); }

다음은 2의 4승을 구하는 프로그램을 재귀함수와 일반 반복함수로 구현한 코드이다. 일반 반복문 함수는 건너뛰고 재귀함수 부분을 보면 기본 부분 (Base Part) 와 유도 부분 (Inductive Part)로 나누어서 구현되어있다.

처음에 4를 넣고 기본 부분에서 판별, 1이하가 아니므로 유도부분으로 가서 재귀호출을 한뒤 계속해서 power가 1보다 작아질 때까지 자신을 호출한다. [그림 2]에 보이듯이 재귀함수는 반복적으로 스택을 사용하는것을 볼 수 있다.

---

[그림 3] 선택정렬 ( Selection Sort }

//일반 //일반 void iteratorSelectionSort(int *ary, int n) { int t; for (int i = 0; i < n ; i++) for (int j = 0; j < i ; j++) { if (ary[i] < ary[j]) { t = ary[i]; ary[i] = ary[j]; ary[j] = t; } } } //재귀 void recursiveSelectionSort(int *ary, int n) { int maxIndex = 0, temp = 0; for(int i = maxIndex; i < n; i++) if (ary[i] > ary[maxIndex]) maxIndex = i; //printArray(ary, n); temp = ary[n - 1]; ary[n - 1] = ary[maxIndex]; ary[maxIndex] = temp; if (n > 1) // 사이즈 1되면 종료 recursiveSelectionSort(ary, --n); }

다음코드는 오름차순 선택 정렬을 일반함수와 재귀함수로 나타낸 코드이다. 선택정렬은 하나씩 정렬해가며 정렬된 부분은 건드리지 않는 방식의 정렬과정이기때문에 재귀호출의 기본부분은 배열의 사이즈가 1이 되면 종결시키도록 만들었다.