[강의] 11월 22일 수업정리

오늘의 수업은 재귀 함수에 대한 수업이었다.

 

1. 재귀 함수 

 

1.1 재귀와 반복

보통 재귀와 반복이 많이 비교가 된다. 우리가 흔히 사용하는 for문이나 while문과 같은 반복 연산을 가리킨다.

항상 그런 것은 아니지만 많은 경우에 재귀로 처리할 수 있는 문제는 반복으로도 처리할 수 있고 반대로 반복으로 처리할 수 있는 것은 재귀로 처리할 수 있다. 어떤 방법으로 문제를 해결하느냐는 프로그래머의 마음이지만 때로는 반복코드보다 재귀 코드를 사용했을 때 더 이해하기 쉬운 코드가 될 때가 있다. 그러므로 우리는 두 가지 방법을 모두 명확하게 알고 있어야 한다. 

 

 

1.2 재귀 함수 

재귀 함수란 자기 자신을 호출하여 작업을 수행하는 함수이다.
재귀는 단순히 반복문처럼 동작한다고 이해해서는 안 된다. 함수가 호출될 때마다 새로운 함수 호출 스택 공간이 생성되며, 호출이 반복될수록 이 공간이 계속 쌓이는 구조이다.

• 재귀의 작동 원리
  재귀 함수는 특정 분기 조건(종료 조건)까지 자기 자신을 계속 호출하며, 이러한 특성 때문에 반복문으로 구현할 수 있는 로직은 재귀로도 구현할 수 있고, 반대로도 가능하다. ( 물론, 효율이 나오지 않아 반대는 잘하지 않는다 )
• 재귀의 유용성
  재귀 함수는 큰 작업을 작은 단위의 동일한 작업들로 나눌 수 있을 때 매우 유용하다.
  또한, 목표 작업을 간단한 동작과 목표 작업을 변형한 작업으로 단순화할 수 있을 때도 효과적이다.
• 재귀의 본질
  재귀는 스택 구조를 활용합니다. 함수가 호출될 때마다 새로운 공간이 생성되어 데이터가 저장되며, 종료 조건에 도달한 뒤에는 그 스택을 역순으로 돌아오며 작업이 진행됩니다.
  따라서 재귀는 "작업 후 이전 상태로 돌아가는" 구조를 가지고 있습니다.
  • 데이터는 Call by Value로 전달되며, 포인터나 참조(Reference)를 사용하면 값을 반환할 수도 있다.
  • 반복문처럼 동작하지만 반복문 그 자체는 아니.

 

1.3 재귀 함수의 깊이와 넓이

• 재귀 함수의 깊이는 제한이 존재하며, 4,000번 이하의 호출까지만 가능하다.
• 반면 넓이는 제한이 없기 때문에 재귀 호출 내에서 다양한 분기를 생성할 수 이 씨.

 

1.4 장점

• 변수 감소
  재귀 함수는 상태를 저장하기 위해 많은 변수를 만들 필요가 없다. 대신, 재귀 호출 시 전달되는 인자를 통해 상태를 관리가 가능하다.
• 간결한 코드
  반복문을 사용하지 않아도 되므로 코드가 간결하고 가독성이 좋아진.

 

 

 

1.5 단점

1. 메모리 사용
   함수 호출마다 스택에 기록이 쌓이며, 반환 전까지 메모리 공간을 계속 차지한다. 즉, 호출 스택이 커지면 메모리 사용량이 급격히 증가해 성능 저하를 초래할 수 있다.
2. 성능 저하
   반복문에 비해 속도가 느려지는 경우가 많기에 상황에 따라 적절한 방법을 선택해야 한다. 

 

팁으로, 재귀 함수 사용 시에는 항상 종료 조건을 명확히 설정하고, 스택 오버플로우 방지를 위해 호출 횟수를 고려해야 한다.

 

1.6 재귀 함수 예제

 

1.6.1 1 ~ n까지 총합을 구하는 재귀함수

#include <iostream>

void add(int nData, int* pResult);

int main()
{
	int nResult{};

	add(10, &nResult);
	printf("%d\n", nResult);
}

void add(int nData, int* pResult)
{

	if (nData < 1)
		return;

	int nResult{};
	add(nData - 1, &nResult);
	*pResult += nResult + nData;
}

 

1.6.2 n ~ 1까지 총합을 구하는 재귀함수

#include <iostream>

void add(int nData, int* pResult);

int main()
{
	int nResult{};

	add(1, &nResult);
	printf("%d\n", nResult);
}

void add(int nData, int* pResult)
{

	if (nData > 10)
		return;

	int nResult{};
	add(nData + 1, &nResult);
	*pResult += nData + nResult;
}