“Fabulous Adventures In Coding : How Not To Teach Recursion” said:
A Joel On Software reader asked the other day for examples of recursive functions other than old chestnuts like Fibonacci or factorial

I’ve never figured out what is difficult about recursion — I’ve always just “gotten it”. Am I that special? Or did I have a good instructor? I vote the latter — the second semester programming (in Pascal) our class was small enough that he had people go to the white board and demonstrate how recursion, linked lists, etc. worked. So you made dang sure that you knew what you were doing! So that may explain when opportunities arise to use recursion, I jump in whole-heartedly.

When you do an analysis of a recursive function, I think it’s easy to get down on big-O numbers. Well, big-O doesn’t take into account hardware, caching, etc. If you use recursion in a function, then you know that you have the function in cache (because you’re running it!) — you just add another item to the stack. And then there’s the fact that recursive functions are usually short and concise — so they are easier to understand (if you are Recursion Enlightened, anyway). So less code to do the work. I consider that a good thing.

So here is my recursion example that finds the greatest common divisor between two integers. My apologies for the bad format — stupid WordPress plugin doesn’t like Python.

def gcd(a,b):
if b == 0:
return a
else:
return gcd(b,a%b)