## Basic and recursion

I’m still reading book about data structures in Basic. Of course, this book didn’t missed an oportunity to show one of usage for stack: recursion. As everybody can imagine, implementation of recursion in plain old Basic is horrible: hard to read, hard to understand. And finally, they demonstrate how to replace recursion with iteration. My main feeling is “never do recursion in Basic”. But reading of this chapter gave me lots of insights.

First, about recursion itself. Lots of books explain it, every Lisp book for beginners have explanation of recursion. They assume that recursion is something which is not tought in school. Yes, that’s right, in school they always prefer iterative approach. I was tough that multiplication is addition of equal values: a*n = a + a + a + … + a (n times). Same thing about factorial. Recursion here is a nice way to avoid those dots and make precise definition of repetitive process by defining such process through itself. But in those cases iteration and recursion give same results, their difference is that recursion is more beautiful but harder to understand. In programming it’s often better to use approach which is simpler to understand. Also, in Basic recursion is not as beautiful as in math, so for Basic iteration for such tasks is a better solution.

There are other cases where recursion is natural: solving “Hanoi towers”, doing binary search in lists and trees. This “naturality” comes from fact that process itself is really recursive or data structures used are recursive. Unfortunatelly, in Basic such data structures are represented in some ugly way, so their recursive nature is not helping to solve task beautifully.

Recursion is a term which belongs to semantics of data structures and algorithms. If you really want to design data structures and algorithms in this way, you should better use programming language which supports semantics of “recursion”. For data structures this means pointers/references, for algorithms it means invokations using stack.

Above is just a concrete case of principle “use tool appopriate for your task”. Nobody tries to do object-oriented programming in C. Nobody should do recursion in Basic.