[자료구조] 재귀호출(recursion)

 

재귀호출이란?

함수가 자기자신을 호출하는 것이다. c언어로 간단하게 구현해보겠다.

int cycle (int n)
{
	return cycle(n);
}

 

언제 재귀호출 사용?

팩토리얼 함수, 최대공약수 구하기같은 순환적인 문제나 자료구조를 다룰때 사용한다.

 

팩토리얼 함수를 재귀호출 코드로 구현해보겠다.

int factorial (int n)
{
    if (n == 1)  return 1;
    
    return n * factorial(n-1);
}

 

 

재귀호출 코드 구현

1. 문제를 점화식으로 나타낸다. - 재귀호출이 일어날수록 문제의 크기가 작아져야 함을 이용하자.

2. 점화식을 코드로 구현한다

 

 

반복문 대신 재귀호출을 쓰면 좋은 경우 (재귀호출의 장점)

 

- 수학적으로 정의한 규칙을 코드로 구현해야할 경우

팩토리얼을 수학적으로 정의하면 

이런 식이 나오는데 이는 위에서 구현했던 팩토리얼 코드식과 똑같다.

int factorial (int n)
{
    if (n == 1)  return 1;
    
    return n * factorial(n-1);
}

따라서 문제를 귀납법으로 식을 정리했다면 코드를 다 짠거나 마찬가지다.

이 점을 이용하여 수학적으로 정의한 리스트, 트리, 그래프에도 재귀호출이 쓰이고 있다.

 

- 프로그램의 규모가 커진 경우

프로그램의 규모가 커질수록 코드가 복잡해지기 때문에 오류가 생겼을 때 고치기 힘들어진다. 따라서 오류를 최대한 고치기 쉽게 짜기 위해 변수의 사용을 줄여야 한다. 이때 재귀함수가 도움을 준다. 재귀함수는 매개변수 말고는 다른 변수를 쓰지 않는다. 만약 재귀함수를 쓰지 않고 for, while같은 반복문을 쓰게 된다면 i,k,j같은 변수를 많이 사용하게 될것이다.

 

 

 

반복문 대신 재귀호출을 쓰면 안좋은 경우 (재귀호출의 단점)

- 처리속도가 빨라야 하는 경우 

재귀함수는 반복문보다 처리속도가 느리다. 자기자신을 계속해서 호출하고 이전 함수로 복귀해야 한다. 그래서 함수호출, 복귀하는 시간때문에 처리속도가 느려진다. 이 때문에 재귀함수를 쓸때마다 빅오 표기법으로 처리속도를 확인해주어야 한다. 하지만 하드웨어의 발달로 인해 컴퓨터 자체 속도가 빨라져 연산 수가 엄청나게 차이가 나지 않는 이상 반복문과 재귀호출의 처리속도는 비슷하다. 

 

- 메모리를 적게 사용해야 하는 경우

재귀함수는 자기자신을 호출했다가 다시 복귀해야 하는 구조때문에 이전 함수를 저장해야 한다. 따라서 재귀함수는 반복문보다 메모리를 많이 사용하게 된다.

 

 

 

단점 보완 방법 : 꼬리재귀 (tail recursion)

재귀호출의 단점을 보완할 수 있는 방법이 있다.

재귀함수의 처리속도가 느리고 메모리를 많이 사용하는 이유는 함수를 호출한 후 이전함수로 복귀해야 하기 때문이다. 그러니 애초에 복귀할 필요를 없애버리면 이 문제는 해결된다. 재귀함수가 복귀해야 하는 이유는 이전 함수에 수행해야할 작업이 남아있기 때문이다. 따라서 애초에 작업을 다 끝내고 가면 복귀하지 않아도 된다. 꼬리재귀는 이 점을 이용했다. 

int factorial(n, total = 1)
{
	if(n === 1)
    	{ 
        	return total; 
        } 
    return factorial(n - 1, n * total); 
}

꼬리재귀는 매개변수를 이용해 연산한 결과를 다음 호출한 함수에게 전달한다. 위에서는 total이 이 역할을 해준다. 이로써 이전함수로 복귀할 필요가 없어졌다.

단, 꼬리재귀 사용할 때 컴파일 옵션에서 코드 최적화가 되도록 설정해 주어야 한다. 안그러면 꼬리재귀 코드임에도 불구하고 재귀함수처럼 처리될 수 있다.

 

 

 

 

 

 

 

 

참고자료

c언어로 쉽게 풀어쓴 자료구조

c로 배우는 쉬운 자료구조

https://kldp.org/node/134556

재귀함수에 대한 질문입니다. | KLDP