[C] 재귀함수

재귀 함수란 함수를 재호출 하는 것을 말합니다.
재귀에는 직접 재귀 함수와 간접 재귀 함수가 있습니다.

 - 직접 재귀함수 예제 : 자신의 함수를 직접 호출

void a()
{

a();

}

 - 간접 재귀함수 예제 : 다른 함수에서 서로 호출

void b()
{

a();

}
void a()
{

b();

}

간접 재귀함수는 거의 사용되지 않으므로 직접 재귀함수를 공부해 보도록 하겠습니다
재귀함수는 루프와 약간 비슷한 면이 있습니다. 명령어를 반복 처리한다는 것이죠. 다른 점은 명령어들을 반복 처리만 하는 것이 아니라 함수 호출 스택이라는 것을 이용합니다. 그래서 명령어들을 하나의 단위로 다루면서도 스택 자료 구조의 이점까지도 쉽게 얻을 수 있다는 것입니다.

루프처럼 재귀함수는 종료 조건을 잘 만들어야 합니다. 루프에서 종료 조건이 중요한 것처럼 재귀함수도 종료 조건이 중요합니다.
종료 조건이 맞지 않으면 재귀함수도 이론상 무한 루프에 빠집니다.

함수 호출이 스택을 사용하므로 재귀 함수는 아래 예제와 같은 특징을 갖습니다.

void Print(int n)
{

printf("start : %d\n", n);
if(1<n) print(n-1);
printf("end : %d\n", n);

}

void main()
{

Print(3);

}

결과:
start : 3
start : 2
start : 1
end : 1
end : 2
end : 3

아래 Print()함수가 두개면 출력 결과는?

void Print(int n)
{

printf("start : %d\n", n);
if(1<n)
{

Print(n-1);
Print(n-1);

}

printf("end : %d\n", n);

}

void main()
{

Print(3);

}

결과:
start : 3
start : 2
start : 1
end : 1
start : 1
end : 1
end : 2
start : 2
start : 1
end : 1
start : 1
end : 1
end : 2
end : 3

그림으로 패턴을 이해했다면 쉽습니다.
트리로 그려보도록 하겠습니다.