[Algorithm] 재귀함수

참고한 블로그 : https://blog.naver.com/tipsware/221423058988

* 재귀함수의 장점 ? 반복문 사용을 줄임으로써 효율적인 코드를 작성할 수 있다.

* 재귀함수란 ? 함수가 자신을 다시 호출하는 구조로 만들어진 함수이고, 이렇게 호출되는 것을 재귀 호출이라고 함.

예를 들어, 1부터 10까지 더하는 프로그램을 보자.

#include<stdio.h>

int main(){

int i, sum = 0;

printf("Sum = ");

for(int i=1; i<=10; i++) sum = sum + i;

printf("%d",sum);

}

이 코드의 결과는 55로 나오지만 반복문을 사용한 것을 볼 수 있다.

#include<stdio.h>

int RangeSum(int a)

{

if(a==1) return a; // a 값이 1이 되면 재귀 호출을 중단!!

return RangeSum(a-1)+a;

}

int main()

{

int sum;

printf("Sum : ");

sum = RangeSum(10);

printf("%d\n",sum);

return 0;

}

결과는 동일하게 55가 출력된다.

재귀 호출의 흐름을 이해하기 위해 정리해보았다.

return에 작성한 코드를 보면,

RangeSum(10) = RangeSum(9) + 10; 임을 알 수 있다.

여기서 RangeSum(9)는 또 RangeSum(8) + 9 로 구성되고,

결국에는 ..

RangeSum(1) + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 임을 알 수 있고,.

a 가 1일때는 1을 리턴하므로 

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 과 같이 표현할 수 있다.

즉 결과는 55로 출력이 된다.

재귀 호출을 잘 활용하면 복잡한 알고리즘을 아주 단순하게 표현이 가능하다.