[기초]재귀

재귀는 말 그대로 자기 자신을 호출하는 것이다.

재귀를 설명할 때의 가장 간단한 프로그램은 역시 피보나치 수열이다.

피보나치 수열은 자기앞의 두 수의 합이 자신의 값이 되는 것이다. 그리고 자기 앞이 존재하지 않는 1, 2번째의 경우 1로 설정된다. 따라서 수열의 모양은 아래와 같다

1 1 2 3 5 8 13 21 34 55.....

이것을 함수로 나타낸다면

int fibo(int index)

{

if(index <= 0)

return 0;

if(index == 1 || index == 2)

return 1;

return fibo(index - 1) + fibo(index - 2);

}

같은 형식이 될 것이다.

재귀의 경우 전부 루프로 나타낼 수 있다고 한다.

c++에서 재귀함수의 문제점이라면

1. 함수이므로 스택이 쌓이면서 메모리 사용양이 증가한다.

2. 위와같은 이유로 느려진다.