[C++] 1-4 재귀함수 설명 및 예제

재귀함수란?

   재귀 함수(recursive call)이란 함수가 자기 자신을 다시 호출하여 실행하는 함수를 말한다. 함수가 호출되면 실인수를 전달받는 가인수들의 값과 그 함수 내에서만 사용되는 지역변수들의 값은 메모리 상의 스택(stack)이라는 임시 메모리에 저장된다. 함수의 실행이 종료되면 지역변수들은 스택 메모리에서 사라진다. 

   만약 재귀 호출의 회수가 많아지면 호출된 횟수만큼 지역변수들의 메모리 영역이 새로운 스택 메모리에 쌓이게 된다. 따라서 함수의 과도한 재귀 호출은 스택 메모리의 이용을 증가시켜 'stack overflow' 오류를 발생시킬 수 있다.

 

 

예제

#include <iostream>
using namespace std;
int fact(int n);	//함수의 원형 선언

int main()
{
	int a, b;
	cout << "a? ";
	cin >> a;
	b = fact(a);	//함수 호출	
	cout << a << "!= " << b << endl;
	return 0;
}

int fact(int n)		//사용자 정의 함수
{
	if (n == 1)
		return 1;
	else
		return (n * fact(n - 1));	//함수의 재귀 호출
}

결과
a? 5
5!= 120
※ 이 재귀함수의 예제는 재귀 호출을 이용해서 factorial 값을 구하는 것이다. 함수의 재귀 호출이 이루어지는 경우, 반드시 return문 등을 이용해서 재귀 함수를 종료시켜야 한다. 
※ 키보드로 입력한 a의 값(실인수) 5이 피 호출 함수의 가인수 n에 전달된다. n=1이 아니므로 fact(5)에서 return (5*fact(4)를 실행하여 main함수로 반환하기 전에  fact(4)를 실행한다. 이런 식으로 반복하여 n=1이 되면 함수가 종료되고 main함수로 넘어간다. 

 

 

참고

1. 장인성 외 5인, (초보자도 쉽게 따라 할 수 있는) C++프로그래밍, 광문각, 2017.02.13