Generally speaking, recursion can come in two flavors: head recursion and tail recursion.

No, it's not watching a dog run around in circles until its head touches its tail. We have to admit that it is a feat of innate biological instinct to see something moving and want to chase that thing.

Even when it's on your own body.

Dog days aside, probably the most popular form of recursion (by our very unofficial consensus) is tail recursion. In tail recursion, the recursive step comes last in the function—at the tail end, you might say. The function checks for the base case and returns if it's successful. Then at the end of the function—the tail—the recursive case runs only if the base case hasn't been reached.

For example, check out a basic recursive function that counts down to zero.

FUNCTION countDown(number){
     IF( number == 0 ):
          RETURN 0
     END IF
 
     RETURN countDown(number - 1)
END FUNCTION

See how that base case of number equaling 0 comes first and the recursive case runs only after the base case is unsuccessful? That's tail recursion at its finest.

Head recursion looks more like this:

FUNCTION countDown(number):
     IF( n > 0 ):
          RETURN countDown( number - 1 )
     END IF
 
     RETURN 0
END FUNCTION

Wait.

These do exactly the same thing. They even have the same conditionals but inverted. Why bother?

It's simple: pick the option that works best for your case. If the cases flow more naturally by running through the recursive cases first, write them first. If it feels more natural to spell out the base case and then get into the recursion, write out the base case first. Mostly, it's a matter of readability. If you write a method using tail recursion and can't make heads or tails of it (yeah, we groaned at that one too—if only we'd stuck with the dog analogies), try rewriting it with head recursion to see if it makes more sense.

Some people also prefer one over the other, so you'll need to understand both ways when you're reading other people's code.

When figuring out the recursive method, you should always start with the base case so that you know what you're working towards. As for how you order it in code: that's up to you.

Just try to keep from biting off your own (code) tail.