25. 리커젼 (Recursion)에 대한 고찰 2

1. 개요

요즘들어 알고리즘을 작성하면서 어떻게하면 코드를 좀 더 줄일 수 있는지 생각하다보니 알고리즘 작성을 못하고 있다.

기존의 내가 배웠던 방법으로 풀어내면 금방이겠지만, 이런식으로는 도저히 정말 사용할 수 있는 수준의 성능이 안나온다.

왜 리커젼을 쓰는지 왜 다이나믹 프로그래밍을 사용하는지 알아내야한다.

그렇게 몇 일을 고민하다가 불쑥 내가 착각하고 있는 게 무엇인지 알아냈다.

내게 있어 리커젼이란 무척이나 어려운 것이었다.

오래 전, 프로그래밍을 포기했을 때 정말 이해가 가지 않았던 원리이기 때문에 이것을 이해하려면 뭐 엄청난 생각의 방법이나

논리가 필요한 줄 알았다. 그런데 아니었다.

그리고 다시 프로그래밍을 시작하면서 리커젼을 작성해봤다. 하지만 이미 연습해본 것이나 작성할 수 있을 뿐, 정말 새로운 것

에 대해서 리커젼을 작성할 자신이 없었다. 뭐랄까 계속 한 곳으로 파고들어가는 그 과정이 머릿속에서 뚜렷하게 안 그려진다

고 해야할까. 그러다 한 책에서 만난 리커젼의 토대. 저번에 올렸던 포스팅에서 나타난 리커젼의 기본 뼈대.

 

 if ( 종료 조건 )

return 종료 값

 else if ( 또 다른 종료 조건 )

return 또 다른 종료 값

 else

return ( 몇 가지 작업 ) and then ( 재귀 호출 )

모든 리커젼은 이 형태에서 출발한다라는 것.

그것을 알았을 때, 뭔가 조금 더 머릿속에서 리커젼에 대한 개념이 잡힐듯 말듯 했지만 뚜렷하게 구상되지는 않았다.

근데 이번에 음 꿈 속에서 리커젼때문에 고민하는 내 모습이 보였는데... 음

결국 리커젼도 반복의 일종이었다.

뭐 거창한 개요에 비하면 참 간단한 사실인데, 내가 정말 제대로 알게된 것은 

반복문이 단지 변수 하나를 단순히 Index 삼아 움직이는 코드라면, 

리커젼도 단지 똑같은 반복이다. 다만 그 Index가 변경을 위해서 기존의 함수가 저장되는 것.

아니아니 이 말도 어렵다. 

그러니까 리커젼도 결국은 출발지에서 어떤 목적지를 향해가는 선형 반복이라는 것이다.

단지 그 선형 반복을 위해 메모리 오버헤드가 크다는 것? 뿐이라는 것이다.

아직도 뭐 완벽히 이것이 이렇고 저것이 저렇다 말은 못하겠지만, 결국 정말로 알게된 것은 이렇다.

머릿속에 트라우마처럼 이것은 어렵다, 어려워서 풀기가 어렵다 한 문제들을 풀어내기 위해 필요한 방법은

어렵고, 거창한 방법론이 아니라 (내 수준의 문제에서는) 단순한 관념으로 풀 수 있다는 것이다.

내 블로그 제목처럼 뭔가 단순한게 모여서 복잡한 것을 이루고 결국 그것도 단순한 형태의 한 뼈대이다.

그러니 최선을 다해 궁리하고 풀어보자.