[C언어] 재귀

재귀는 자신의 보다 작은 인스턴스들로 무엇인가를 정의할 수 있게 하는 강력한 원리이다.

재귀함수는 자신을 호출하는 함수이다.

-->팩토리얼

int fact(int n){

if(n<0)

return 0;

else if(n==0)

return 1;

else if(n==1)

return 1;

else

return n*fact(n-1);

}

재귀호출에서는 스택을 사용하는데 모든 함수 호출이 리턴할 때까지 그것들과 관련된 정보를 유지해야 하므로 재귀 호출이 많은 프로그램에서 많은 메모리를 사용한다. 게다가 활성 레코드의 크기가 크기 때문에 활성 레코드를 생성하고 제거할 때 시간이 많이 걸린다.

재귀함수가 끝없이 계속 반복된다면 스택 오버플로우로 강제 공료된다. 프로그램이 실행될 때 프레임 포인터(Frame Pointer)라고 불리는 특별한 포인터가 스택의 제일 위 부분의 위치를 가리키고 있다. 이 포인터는 스택이 너무 커졌을 때에도 사용된다. 이 때 오류를 알리기 위해 인터럽트가 발생한다.

따라서 이러한 부담이 커지면 반복적인 접근법을 고려해야한다.

또한 꼬리재귀(Tail Recursion)를 사용할 수 있다.

- 꼬리재귀는 재귀 호출이 함수 몸체의 제일 마지막에서 실행되고, 리턴값이 다른 식에 사용되지 않을 때 성립한다.

- 컴파일러가 꼬리 재귀 호출을 발견하면 새로운 활성화 레코드를 스택에 추가하지 않고 현재 활성 레코드에 덮어쓴다.

- 새로운 활성 레코드를 추가하지 않고 현재 레코드에 덮어씀으로써 스택 사용이 현저하게 줄어들고 실제 성능도 좋아진다.

--> 팩토리얼

F(n,a) = a (if n=0, n=1, a는 기본 1)

  = F(n-1,na) (if n>1)

int facttail(int n, int a){

if(n<0)

return 0;

else if(n==0)

return 1;

else if(n==1)

return a;

else

return facttail(n-1, n*a);

}