내일배움캠프 47일차 - 자료구조 & 알고리즘 7주차 : 재귀

 재귀

 - 함수가 자기 자신을 호출하는 것을 일컫는다.
예) 팩토리얼(Factorial)

재귀가 동작하기 위해서는 두 가지 조건이 필요하다.

1) 재귀호출: 자기 자신을 호출하되, 종료지점에 가깝게 문제가 작아진다.
2) 종료조건(Base case): 더이상 호출하지 않는 지점

내려가면서 호출하고, base case(돌아오는 값)을 만나면
거슬러 올라오면서 계산한다.

재귀 함수는 우리가 직접 스택을 만들지 않아도 자동으로 콜 스택을 사용한다.
 - 재귀로 풀 수 있는 것 = 스택 + 반복문으로도 풀 수 있다.
 - 재귀가 더 깔끔할 때가 있고, 반복문이 더 효율적일 때가 있다.

종료 조건이 없으면 발생하는 문제 - 무한 호출

위 사진처럼 재귀호출을 하지않는 시점이 없으면 무한호출이 발생한다.
호출이 지나치게 잦으면(약 1만번 초과) 콜 스택 메모리(보통 1~8MB)가 가득하게 되어 프로그램 크래시가 발생한다.

이를 스택 오버플로우(Stack Overflow)라고 한다.

무한 호출을 방지하기 위해
재귀 전 종료 조건(base case)를 작성해야 한다.

재귀 사용 예시

 - 피보나치 수열 (재귀의 함정)
 - 배열의 합 (재귀적 분해)
 - 거듭제곱 (분할 정복 재귀)