[week 14] C++ 복습_9장 재귀 호출

20211202_C++_공부기록

 

• 재귀 함수
• 재귀 대 반복

---

재귀(recursion)

 

 - 재귀 : 자기 자신을 호출하는 함수

 - 재귀함수는 반드시 정지조건을 가지고 있어야 하며, 그렇지 않으면 무한재귀(infinite recursion)가 발생할 수 있다.

 

• 예제: 계승 계산

#include <iostream>
using namespace std;

int fac(int);

int main()
{
	int num;
	cout << "정수를 입력해주세요: ";
	cin >> num;

	cout << num << "!은 " << fac(num) << endl;
	return 0;
}

int fac(int n)
{
	if (n == 0)
		return 1;
	else
		return n * fac(n - 1);
}

/*
정수를 입력해주세요: 5
5!은 120
*/

 

• 예제 : 피보나치 수

#include <iostream>
using namespace std;

int fib(int);
int main() {
	int index;
	cout <<  "Enter an index for the Fibonacci number: ";
  	cin >> index;
	cout << "Fibonacci number at index " << index << " is "
    		<< fib(index) << endl;
  	return 0;
}

int fib(int index) {
 	 if (index == 0) // Base case
    		return 0;
  	else if (index == 1) // Base case
    		return 1;
  	else // Reduction and recursive calls
    		return fib(index - 1) + fib(index - 2);
}

 

• 예제 : 2^n을 계산하는 재귀함수 작성

#include <iostream>
using namespace std;

int power(int); //함수원형

int main()
{
	cout << "양수를 입력하시오: ";
	int n;
	cin >> n;
	cout << "2 의 " << n << " 제곱은:  " << power(n) << endl;
	return 0;
}

int power(int n)
{
	if (n == 0)
    	return 1;
    else
    	return n * power(n-1);
}

---

재귀 대 반복

 

 - 재귀는 기본적으로 반복문이 없는 반복

 

 - 재귀는 상당한 오버헤드를 발생시킨다. 프로그램이 함수를 호출할 때마다 시스템은 함수의 지역변수와 매개변수 전체에 대한 공간을 할당해야 하므로 많은 시간과 메모리가 필요하다.

 

 - 반복문을 쓰는 것을 권유하지만 재귀를 사용하지 않으면 해법을 찾기 어려운 문제라면 재귀를 사용한다.

 

 - 재귀는 메모리 부족을 발생시켜 runtime error를 발생시킬 수 있으며, 반복보다 더 많은 시간과 메모리를 소비하기 때문에 프로그램 성능이 중요한 경우에는 피한다.

 

• 선택정렬

void selectionSort(double list[], int listSize) {  //실습4
	if (listSize > 0) {
		double max = list[0];
		int maxIndex = 0;
		for (int i = 1; i < listSize; i++) { //가장 큰 수 찾기
			if (list[i] > max) {
				max = list[i];
				maxIndex = i;
			}
		}
		list[maxIndex] = list[listSize-1]; //교환
		list[listSize-1] = max;
		selectionSort(list, listSize - 1); //재귀호출
	}
}
void printArray(double list[], int arraySize) { //배열 프린트 함수
	for (int i = 0; i < arraySize ; i++) 
		cout << list[i] << " ";
}
int main() {
	double list[] = { 9, 1, 2, 5, 4};
	selectionSort(list, 5);
	printArray(list, 5);
	return 0;
}