재귀
재귀란 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘
어떤 문제를 재귀로 푼다는 것은 곧 귀납적인 방식으로 문제를 해결하겠다는 것.
우리가 지금까지 당연하게 생각하던 절차 지향적인 사고를 탈피해야 한다.
1번 도미노가 쓰러지고 이후에 2번 도미노 쓰러지고... 이렇게 연쇄적으로 진행되어 모든 도미노가 쓰러진다는 절차 말고
q번 도미노가 쓰러진다. k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다 까지만 생각한 후 바로 모든 도미노가 쓰러진다는 결론에 도달할 수 있어야 한다.
올바른 재귀 함수는 반드시 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다. 이러한 입력을 base condition 내지는 base case라고 한다.
그리고 모든 입력은 base condition으로 수렴해야 한다.
이 두 조건 중 어느 하나라도 지켜지지 않는다면 재귀 함수는 결과를 내지 못하고 무한히 돌아가다가 런타임 에러가 발생하게 될 것이다.
재귀에 대한 정보
- 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자신에게 넘겨줄지 명확하게 정해야 한다.
- 모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다.
- 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만 메모리/시간에서는 손해를 본다.
재귀는 적재적소에 사용하면 코드가 간결해지지만 함수 호출이 꽤 비용이 큰 연산이기 때문에 메모리와 시간에서는 손해를 본다. 그렇기 때문에 굳이 재귀를 쓰지 않아도 구현에 큰 어려움이 없으면 재귀 대신 반복문으로 코드를 짜는 것이 좋지만 재귀 없이 구현을 하면 코드가 너무 복잡해지는 일부 문제들은 재귀로 구현을 하는 것이 좋다. 문제 풀며 경험으로 익혀라.
재귀에 대한 정보 2
- 한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있다.
피보나치 문제와 같이 자기 자신을 여러번 호출하는 과정에서 중복된 계산이 계속 발생해 시간 복잡도가 말도 안 되게 커져버린 상황이고 이 문제는 재귀 대신 다이내믹 프로그래밍이라는 방법을 이용해 O(n)에 해결할 수 있다.
재귀에 대한 정보 3
1. 재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 됨.
재귀 함수가 자기 자신을 부를 때 스택 영역에 함수에 대한 정보가 누적된다. 이 스택 영역은 메모리 구조에서의 스택 영역을 말한다.
스택 메모리가 작게 제한된 곳에서 문제를 푸는데 본인의 풀이가 재귀를 깊게 들어가는 풀이라면 어쩔 수 없이 재귀 대신 반복문으로 문제를 풀어야 한다. 참고로 스택 메모리에는 지역변수도 들어간다.
1629번 - 곱셈
해당 문제를 절차지향적인 사고 대신 귀납적인 사고로 사고할 수 있어야 한다.
해당 아이디어 사용.
11729번 - 하노이 탑
해당 문제야 말로 절차지향적인 사고를 완전히 탈피해야 풀 수 있다.
n=1일 때 되고 n=k일 때 되면 n=k+1일 때 된다는 사고.