Ahhhh, recursion

I had a talk with a coworker of mine where  he chided some people for writing recursive functions in embedded code.  While admittedly you do need to be careful in certain languages in certain environments (where you might have a small stack space), I still think recursion has gotten a bum wrap.  I'm surprised how many of my colleagues dismiss recursion out of hand.  Of course the vast majority of my coworkers are also C programmers which explains a lot.

I realized at work today that I have done more recursive functions in the last 5 months than in my 4 years of working, 3 years of school, and my 1yr of programming prior to going to school (notice how employers never count the programming you did in school?).  I actually ran into a perplexing problem that at first I thought I could solve iteratively, but I eventually wound up doing recursively.

The hardest  part for me about recursion is knowing where in the call stack I am, and knowing when I should return some value I want.  For example, let's do a simple interest calculator function in python...

def calcInterest(principal, savings, interest, years):

    yearly_interest = principal * interest

    principal += savings + yearly_interest

    print "%d: Principal = %d\n" % (years, principal)

    if years:

        calcInterest(principal, savings, interest, (years - 1))

    else:

        return principal

Do you see the problem with the above function?  No?  Look at the return.  It appears that the base case is when years == 0, so we fall into the else statement and we return the principal right?

Not exactly.  Remember what we are actually doing...we are chaining together a series of functions, so ask yourself what really is returning?  The correct function would be this:

def calcInterest(principal, savings, interest, years):

    yearly_interest = principal * interest

    principal += savings + yearly_interest

    print "%d: Principal = %d\n" % (years, principal)

    if years:

        return calcInterest(principal, savings, interest, (years - 1))

    else:

        return principal

 I have been bitten enough by this that I thought I would pass it along.  Of course, recursion in a language like python or Java which has mutable objects is different from clojure where the objects are immutable.  So how would I write a interest calculate in clojure?

(defn calc-interest
         [ principal savings interest years ]
         (loop [ p principal
                    y years ]
           (if (= 0 y)
             p
             (recur (+ (* p interest) savings p) (dec y)))))

Note that the clojure function goes through the loop one less time than the above python equivalent.  In some ways, recursion in clojure is easier than it is in mutable languages, because the changing state is always being rebound.  If anything the loop/recur in clojure is more similar to a while loop than anything else.  In clojure, the function can directly call itself (self-recursion) but then you have to watch out about potential stack overflow problems.  That's why it's better to use the loop/recur form when possible.