재귀함수에 대한 이해

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

재귀함수의 개념은

자기자신의 함수를 실행하면서

자기자신을 복사하는 개념입니다.

복사본으로 표현하면

원본에서 자기함수를 만나면 복사되서

복사본1에서 자기함수를 만나면 또 복사되서

복사본2에서 자기함수를 만나면 또 복사가 되서

이렇게 계속 복사가 되는식으로 무한하게 실행된다.

그래서 탈출조건을 걸어두고 사용해야한다.

탈출조건의 예

return 값이 0이 되기전까지 계속 재귀하다가

0이 되면 결국 차례차례 다시 올라오면서

함수가 차례차례 종료되고 원본으로 오면

모든 재귀함수가 종료되는것을 볼수있다.

소스로 이해하기

int Factorial(int n)

{

if(n==0)

 return 1;

else

 return n*Factorial(n-1)

}

팩토리얼 재귀함수다.

만약 n=0이라면 1로 반환하고

아니라면 n*F(n-1)을 반환한다.

그러면 n이 3이라면

else를 실행하고 반환값 : n*Factorial(n-1)

Factorial(n-1)은 재귀함수이기때문에

이번엔 n-1의 값인 2로 함수를 재귀한다.

n=2, else를 실행하고

반환값 : n*Factorial(n-1)

Factorial(n-1) 2-1 = 1 로 재귀함수를 실행한다.

n=1, else를 실행하고

반환값 : n*Factorial(n-1) 1-1=0 으로 재귀함수를 실행한다.

n=0이 되고 if조건에 만족하여 1의 값을 반환한다.

그리고 n=0의 함수가 끝나고 n=1로 올라간다.

n=1에서 반환값 : n*Factorial(n-1)에서 

Factorial(n-1)부분에 1의 값을 반환받고

n=1 * Factorial(n-1)=1, 즉 1*1을 하게 되고 값이 1이 된다.

그 값을 n=2에 있는 Factorial(n-1)에 반환한다.

그러면 이전과 같은 원리로 2*1 = 2가 되고, 또 그 반환값을

n=3에 있는 Factorial(n-1)에 넘겨준다.

그래서 3*2=6이 된다.

3!=6이다.