재귀 (recursion)

재귀라는 뜻이 무엇인가?
Computer Science에 있어서 자신을 정의할 대 자신의 재참조하는 방법
재귀를 왜 쓸까? 특정 케이스에서 쓰게 되면 코드가 간단해진다.

재귀 함수

자기 자신을 호출하는 함수.

재귀 함수는 쓰여도 트리 구조에서 쓰인다. 그 외에는 잘 안 쓰인다. 왜 안 쓰이냐?
재귀 잘 안 쓰는 이유는 컴퓨터의 메모리에 있다. 만약 재귀 함수에서 조금 잘못 적기라도 한다면 함수가 스택(stack)에 무한히 쌓이게 될 수도 있다. 이 상황에서 스택 오버플로우(Stack Overflow)라는 것이 발생한다.

따라서, 특정 조건이 되었을 때 반드시 return이 되어야 한다.

재귀로 문제 해결 방법

1. 문제를 동일한 방식으로 계속 쪼개기
   -> 쪼개는 방식이 cursive case

2. 더이상 안 쪼개지면 그것이 base case
   -> 재쉬 함수의 탈출 조건

쪼개졌던 문제가 한 번에 해결!

재귀를 사용하는 상황

• 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
• 중첩된 반복문이 많거나 반복문의 중첩 회수를 예측하기 어려운 경우
• Tree, Graph 구조 (자료구조) 순회할 때 - dfs(트리 순회 방법)

재귀를 잘 사용하지 않는 이유

잘 못 돌리면 Stackoverflow로 터진다... 프로그램이 터지는 건 굉장히 심각한 문제. (메모리) 만약 root 부분에서 function A를 call 하고 function A에서 function B를 call하고 function B에서 function C를 call하면 function C는 전역 변수, function A, function B, function C에서 쓰이는 모든 환경에 접근 가능하다. 이는 클로저(closure)의 개념과 관련있다. 클로저는 외부 함수의 변수에 접근할 수 있는 내부 함수를 의미한다. 이를 통해 내부 함수는 외부 함수의 변수에 계속 접근할 수 있다. 클로저를 사용하는 경우, 내부 함수가 외부 함수의 변수에 접근할 수 있기 때문에 추가적인 메모리를 사용할 수 있다. 외부 함수의 렉시컬 환경은 클로저가 존재하는 동안 유지되어야 하기 때문에 메모리 사용량이 증가 할 수 있다. 하지만, 메모리 사용에 대한 실질적인 영향은 상대적이다. 대부분의 경우 클로저에 의한 메모리 사용량은 무시할 정도로 작거나 최적화 된다. JavaScript 엔진은 메모리 관리를 최적화하기 위해 여러 기술과 알고리즘을 사용한다. 클로저를 적절하게 사용하면 코드의 가독성과 유지보수성을 높일 수 있다. 그러나 과도한 클로저 사용이나 잘못된 클로저 관리는 메모리 누수(memory leak)를 발생시킬 수 있다. 이를 주의해야 한다.

재귀로 짤 수 있는 것들은 반복문으로 대신할 수 있다.단, 예쁘지 않거나 복잡하게 될 거다.

유지보수가 힘들다. => 살짝 변하게 되면 에러가 날 확률이 높아진다.

마지막으로

자료구조에서 기본적인 스택과 큐에 대해서 알아봐야겠다.