재귀 (recursion)

재귀

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

 

어떤 문제를 재귀로 푼다는 것은 곧 귀납적인 방식으로 문제를 해결하겠다는 것.

 

 

재귀 함수의 조건

특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함(Base condition)

모든 입력은 base condition으로 수렴해야 함

-> 이 두 조건 중 어느 하나라도 지켜지지 않는다면 재귀 함수는 결과를 내지 못하고 무한히 들어가다가 런타임 에러가 발생하게 된다.

 

1. 재귀에서는 함수를 명확하게 정의해야 한다. 

함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 함.

모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있음.

 

재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만 메모리/시간에서는 손해를 봄. (함수 호출은 꽤 비용이 큰 연산) 

굳이 재귀를 쓰지 않아도 구현에 큰 어려움이 없으면 재귀 대신 반복문으로 코드를 짜는게 좋다. 

재귀 없이 구현을 하면 코드가 너무 복잡해지는 일부 문제들은 재귀로 구현을 하는게 좋다.

 

2. 한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있음

ex) 피보나치. 이미 계산한 것을 또 계산하는 일이 빈범함. -> 다이나믹 프로그래밍으로 해결

 

3. 자기 자신을 부를 때 스택 영역에 계속 누적이 됨

 

아래 영상을 보고 정리한 내용입니다.

https://youtu.be/8vDDJm5EewM