Don’t have much to write. I might have an interview coming up, so I decided to brush my knowledge of data structures and algorithms. While I was working on link lists, I realized that a big change in how I approached to a data structure problem had come about. There was a time where I would always try to come up with a solution that was always iterative. I understood (or thought I understood) recursion and pointers, but didn’t dare to apply it in the problems I had to solve. I think the reason for that was that I always taught that in order to prove the correctness of a recursive algorithm, I should trace the series of recursive invocation of a recursive algorithm. Being somewhat inept at abstract thought, that was never a good experience.
Plus, the so-called rumor by some “experienced” people that recursion was bad, and that nobody used it in production code, left me biased against recursion.
My attitude towards recursion began to change when I begain to look at Haskell and Prolog. The best way of defining a recursive function was not to think of repeated invocations, but to define the various cases that the algorithm was supposed to cover. Suddenly the abstraction became easier to handle. The repeated invocation technique would actually decrease the abstraction, reducing “understandability”. Today, recursion tends to come to me more naturally than an iterative algorithm. When I looked over the link list excercises that I had coded, almost all of them where recursive. Now I have to convert them to an iterative form just to make sure I understand that bit too. Using recursion made me focus on the problem at hand, rather than coding intricate logic of
if...else blocks for handling special conditions for handling the beginning and/or ending of link lists.