재귀(recursive) 함수

재귀 함수

자기 자신을 다시 호출하는 함수

 

재귀 함수 사용시

 

• 재귀 함수의 종료 조건을 반드시 명시해야 한다.
• 종료 조건을 명시하지 않으면 무한히 호출될 수 있다.

재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있음

컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.

- 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수 사용 가능

#include <iostream>
using namespace std;

void recursive(int i)
{
	if (i == 100)
		return;
	cout << i << "번째 재귀함수에서 " << i + 1 << "번째 재귀함수를 호출" << endl;
	recursive(i + 1);
	cout << i << "번째 재귀함수를 종료" << endl;
}


int main(void)
{
	recursive(1);

	return 0;
}

위를 보면 가장 마지막에 호출된 함수가 먼저 종료된 후 마지막으로 처음에 실행한 함수가 종료된다.

 

재귀함수를 호출하면 Stack에 쌓였다가 조건이 만족되면 종료되면서 stack에서 사라진다.

 

 

예시 -> 팩토리얼 구현

#include <iostream>
using namespace std;

/* 반복문으로 구현 */
int factorial_iter(int n)
{
	int result = 1;
	for (int i = 1; i < n + 1; i++)
		result *= i;
		
	return result;
}

/* 재귀로 구현 */
int factorial_recu(int n)
{
	if (n <= 1)
		return n;
	else
		return n* factorial_recu(n - 1);
}


int main(void)
{
	cout << "Iterative 팩토리얼 : " << factorial_iter(4) << endl;
	cout << "Recursive 팩토리얼 : " << factorial_recu(4) << endl;

	return 0;
}

 

예시 -> 최대공약수 계산

유클리드 호제법 :  2개의 수로 최대공약수를 구하는 알고리즘의 하나

(호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘 - 위키피디아 참고)

 

- 자연수 A, B에 대하여 (A>B) A를 B로 나눈 나머지를 N이라고 가정

- 이 때, A와 B의 최대공약수는 B와 N의 최대공약수와 같다.

 

#include <iostream>
using namespace std;


/* 재귀로 구현 */
int Euclidean_algorithm(int a, int b)
{
	cout << a << " " << b << endl;

	if (a % b == 0)
		return b;
	else
		return Euclidean_algorithm(b, a % b);
}


int main(void)
{
	cout << Euclidean_algorithm(144, 60) << endl;

	return 0;
}

유클리드 호제법 계산

 

 

 

재귀 함수 이용시 : 복잡한 알고리즘을 간결하게 작성 가능

 - 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있음

 

모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현 가능

 

컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.

 

 

 

내용 및 코드 참고

www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3