재귀함수에 대하여!

재귀함수

자기자신을 재호출하는 형태로 정의된 함수를 재귀함수라 합니다.

 

• 재귀함수는 무한루프에 빠질 수 있다.
• 탈출조건을 설정해줘야 한다. 그러지 않으면 오버플로우에 빠진다.

 

재귀함수 대표적인 예시 : Factorial n!

 

int Factorial(int num)
{
	if(num == 1)
    	return 1;
    return num * Factorial(num - 1);
}

 

 

 

재귀함수의 특징

함수가 자기자신을 호출할때마다 메모리가 쓰입니다.

그리하면 연산이 많아져서 비용이 커지기에 성능이 좋지 않으며

프로그래머 입장에서는 직관적인 표현은 아닙니다.

 

C언어가 재귀적 함수호출을 지원한다는 것은 그만큼 표현할 수 있는 범위가 넓다는것을 의미

C언어의 재귀함수를 이용하면 재귀적으로 작성된 식을 그대로 코드로 옮길 수 있다.

 

 

하노이 타워

하노이의 탑(Tower of Hanoi)은 3개의 막대가 있고 첫번째 막대에 N개의 서로 다른 크기의 원반이 쌓여있습니다.

 

하노이 탑 규칙

• 한 번에 움직일 수 있는 원반은 맨 위에 놓여 있는 원반 하나뿐이다.
• 원반위에 더 큰 원반을 쌓을 수 없다.

하노이 탑은 재귀함수의 예시중 하나이며 아래의 코드로 실행됩니다!

void Hanoi(int num , char from, char by, char to)
{
	if (num == 1)
	{
		printf("%d번째 원반 %c => %c \n", num, from, to);
	}
	else
	{
		Hanoi(num - 1, from, to, by);
		printf("%d 번째 원반을 %c => %c \n", num, from, to);
		Hanoi(num - 1, by, from, to);
	}
}

 

반응형