My Brain Hurts: recursion with factorials

With pencil and paper in hand, I have no problem with recursive patterns. Fibonacci schmibbo-hotsytotsy. Factorials schmacks-Oreos.

“Write a recursive function to …” blah mork loopy loo let me leave the interview now so you can continue with someone better, and I can drown my sorrows in two scoops of ImNotWorthy. 

I know this because it was not until I was asked to demonstrate recursion in a mock interview (I requested this topic), that I saw that my comprehension was passive. I understood it when I saw it. … ish. Understood-ish. But there was absolutely no active comprehension. I could not do it on my own. No ish. Nuthin. Fear? Nerves? A pebble in my shoe?

It is that whole “snake eating it’s tail” that was throwing me. I could not recreate what was going on. There is no stack with pencil and paper. I can write it out and do them in my head until I needed a calculator, but even with a calculator, all I needed was a line:

5! = 5 x 4 x 3 x 2 x 1

I understood stacks in other terms (callbacks, pancakes), but the recursion was hurting my brain, until I made it a literal stack in my head. I was treating the part of the code block after the base case as a spiral when (for me) thinking about it as slapping 3×5 cards down. No wonder I didn’t understand the stack; I wasn’t treating it like one.

I’ve been playing with recursion and different tasks as I plow through books on algorithms and tech interview skills. Factorials and Fibonacci are the easier ones to grasp. Not easy. EasIER. Comparative. Like farts smell better than decomposing bodies. They don’t smell good, just better.

I wouldn’t say that I could whip out recursion any time, and I know that I wouldn’t want to with factorials (O(n2) and all that), but I’m getting there. I spent some time on JSFiddle and with my markers to play.

factorial_recursion

The code is old news.

const factorial = n => {
if(n===1){
return 1; //my base case
}
return n * factorial(n - 1); //my nut case
}

I did not set include checking to see that n is a non-negative integer. That was not the point of my doodling because checking for that was not the hard part. This post isn’t about a fully-tested function to return the factorial of a number; this is about me getting the recursive part.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s