[자료구조/알고리즘] 재귀

• 분할정복에서 재귀함수가 쓰임
•  메모리를 많이 소요한다는 재귀의 단점을 보완하기 위해 동적프로그래밍을 사용
• 코딩테스트 문제 중에는 깊은 복사/옅은 복사를 구별하는 문제들 존재
• String.contains() 같은 메서드는 내부적으로 순환을 하기 때문에 재귀와 같이 쓰면 복잡도가 매우 높아질 수 있음

 

- 재귀함수란

• 자기 자신 호출을 반복해서 호출하는 함수

 

- 재귀함수 장점

• 코드가 간결함
• 변수를 여러 개 사용할 필요가 없음

 

-  재귀함수 단점

• 코드의 흐름을 직관적으로 알기 힘듬
• 반복하여 메서드를 호출하면 스택 메모리를 많이 사용

 

-  재귀적으로 사고하는 법

• 재귀 함수의 입력값과 출력값 정의
• 문제를 잘게 쪼개기
• 문제를 쪼개고 경우의 수 나누기( ex) 더 이상 쪼갤 수 없는 경우/ 그렇지 않우 경우)
• 단순한 문제 해결(base case/ 탈출 조건)
• 복잡한 문제 해결( recursive case ) head와 tail