[바킹독의 실전 알고리즘] 0x0B강 - 재귀

 

알고리즘 설명

재귀

하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘

 

절차 지향적인 사고를 탈피해야 한다!

함수 호출 과정을 하나하나 따라가는 대신 귀납적인 사고를 통해서 이해하도록 하자.

 

재귀 함수의 조건

• 특정 입력에 대해서는 반드시 자기 자신을 호출하지 않고 종료되어야 한다.(Base condition)
• 모든 입력은 Base condition으로 수렴해야 한다.

 

재귀에 대한 정보

• 함수의 인자로 무엇을 받고, 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 한다.
• 모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다.
• 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만, 메모리와 시간에서는 손해를 본다.
  -> 굳이 재귀를 쓰지 않아도 구현에 큰 어려움이 없으면 반복문을 사용하는 것이 좋다.
• 한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있다.
  -> 이미 계산한 것을 또 계산하는 일이 빈번하게 발생하기 때문이다.
• 재귀 함수가 자기 자신을 부를 때 스택 영역에 함수에 대한 정보가 계속 누적된다.

 

 

출처: 바킹독님 블로그