[알고리즘] Recursion 2

문자열의 길이 계산

if the string is empty
    return 0;
else
    return 1 + the length of the string that expcludes the first character;

수도 코드 형태로 적은 것입니다. 받은 문자열에서 첫글자를 뗀 나머지 분자열을 받는 것입니다. 

 

int length(char *str)
{
	if (*str == '\0')
		return 0;
	else
		return 1 + length(str + 1);
}

 

문자열의 프린트

void printChars(char *str)
{
	if (*str == '\0')
		return;
	else
	{
		printf("%c", *str);
		printChars(str + 1);
	}
}

 

문자열을 뒤집어 프린트

void printCharsReverse(char *str)
{
	if (*str == '\0')
		return;
	else
	{
		printCharsReverse(str + 1);
		printf("%c", *str);
	}
}

 

순차 탐색

int search(int data[], int n, int target)
{
	if (n <= 0)
		return -1;
	else if (target == data[n - 1])
		return n - 1;
	else
		return search(data, n - 1, target);
}

 

최대값 찾기

int findMax(int n, int data[])
{
	if (n == 1)
		return data[0];
	else
		return max(data[n - 1], findMax(n - 1, data));
}

 

2진수 변환해 출력

void printInBinary(int n)
{
	if (n < 2)
		printf("%d", n);
	else
	{
		printInBinary(n / 2);
		printf("%d", n % 2);
	}
}

 

 

Disjoint Sets, 배열 A의 A[0], ..., A[m-1]과 배열 B의 B[0], ... , B[N-1]에 정수들이 정렬되어 저장되어 있을 때 두 배열의 정수들이 disjoint한지 검사한다. 

bool isDisjoint(int m, int A[], int n, int B[])
{
	if (m < 0 || n < 0)
		return true;
	else if (A[m - 1] == B[n - 1])
		return false;
	else if (A[m - 1] > B[n - 1])
		return isDisjoint(m - 1, A, n, B);
	else
		return isDisjoint(m, A, n - 1, B);
}

 

Recursion vs Iteration

• 모든 순환함수는 반복문으로 변경 가능
• 그 역도 성립 즉 모든 반복문은 recursion으로 표현 가능
• 순환함수는 복잡한 알고리즘을 단순하고 알기 쉽게 표현하는 것이 가능
• 하지만 함수 호출에 따른 오버헤드가 존재 

recursion의 단점은 실행 시간에서 비효율성이 있습니다. 함수 호출에 따른 오버헤드 즉 반복문이라면 for문이나 while문으로 돌면 되는 것을 함수 호출로 대신하기 때문에 눈에 보이지 않는 뒤에서 해주어야 하는 작업들이 많이 있습니다. 

 

예를들면 매개변수를 전달하고, 엑티베이션 프레임 생성 등이 있기에 그런 것들은 오버헤드로 존재하여 똑같은 알고리즘을 recursion으로 구현하고 for문이나 while문 같은 반복문으로 구현했을 때 알고리즘 자체가 동일하다면 상당한 정도의 performance의 차이가 존재할 수 있습니다.