Deja Vu Cat
82 views

What is Recursion? (university assignment edition) Shitty Programming

I was just asked by my housemate a question about recursion. He’s a university student and thought it’d be an excellent idea to leverage his fellow roommate to help him with his assignment.

Unfortunately, I let him down. I explained, “I don’t fully understand recursion. I’ve never seen it at the workplace. That’s not to say you won’t and it could possibly an interview question. But no, I don’t know and I probably should”. How disappointing. As we stood together in the hallway with his laptop balanced on his knee. I knew at this point I should grab a textbook and start reading.

Recursion. I understand the meaning of the word and little else. I’d like to associate it roughly with the ‘cat’ in the Matrix. That’s Deja Vu and I suppose a connection can be formed somehow. It’s when the same thing happens over and over again. It’s recursive. In computer science, we’re talking about a function or method that calls itself. Confused? I am. That’s normal. Think of it like time travel. So let’s try draw a picture to explain this phenomenon.

Recursion drawing

So the outputs are used as the inputs. We have a method/function or some kind of magic box that takes something in and spits something out. Only the ‘out’ goes back ‘in’. That’s cool but I feel like it would just keep looking for eternity. It must need some kind of way to escape right? Well, according to Wikipedia, I would be correct. Using their wonderful recipe analogy for sourdough, I found:

Wikipedia snippet

I’d like to take this opportunity to highlight the second line. Take that university professor!

So we need some conditions to handle the escape cases. If we modify our diagram, we get:

Recursion drawing 2

And if we boot up a quick Console App in Visual Studio:

Recursion Example

What do you think will happen?

And when we run it:

Stack Overflow

Opps

I knew using Int32.MaxValue was a bad idea. It would recurse, 2147483647 times. Well, minus 3 because that’s where it crashed. Let’s just minus 3.

Me failing

HAHAHAHA, that wasn’t expected

It actually is re-cursing. It seems to overflow the stack when it gets down to 3. I don’t understand why. I’m sure someone more clever than I can answer that one. Let’s go with a more conservative value.

Voila!

Odd that we got the StackOverflow exception. I’d imagine that every recursion has to be stored in memory. I don’t actually know how. I’m sure it’s different then a standard loop. It’s strange they both crashed at 3. It crashes randomly with values within the range 12870 – 12890+. The stack must change every time I run it because sometimes it works, sometimes not. I just wonder why it’s always at input = 3. Bizarre.

Part of my housemates assignment is to count the number of calls made to the recursive function. In my case I believe it’s the input number + 2. I suppose I could add another input variable that increments and return it in an array of ints.

Number of calls code Number of calls

This turns out to be incorrect. As his assignment wanted the calls to be output. Every time the Recursion method was run. Simply putting the Console.Write (print) method inside the recursion method would achieve this.

Number of calls modified number of calls modified result

You get the gist of it. Just looking at Wikipedia, I saw this line which relates to the StackOverflows:

This makes a lot of sense given my program crashed all the time. As for being simple. I don’t know about that. I think your standard loops probably make a lot more sense. There’s no need to be clever and use recursion unless it’s absolutely necessary. Just use a loop, it does the same thing and will be easier for others to understand in the event your peers have not been enlightened by recursion (can you blame them? :P)

Same as a loop

I find this a lot easier to understand. Namely because having a recursive function isn’t immediately obvious. A loop however, is very obvious. I see that’s a loop, I recognise it. As long as it’s not zero, it’ll keep going. Honestly, I find that easier to understand. The recursion looks neater if you’re into OCD ‘n shit.

Below is the same algorithm using a loop at In32.MaxValue. It just won’t stop. The Stack does not overflow. It will get to the end, if it hadn’t already been running for an hour because the print function is slow and I can’t be bothered modifying the program to just output the number of recursive calls. But you get the idea.

OMG it wont stop

OMG it won’t stop

The major advantage of the loop, it I can run to the Int32.MaxValue without taking a StackOverflow penalty hit. That is a shit load better than recursion.. I’m sure I’m only tipping the iceberg of recursion. I’m sure there are many ways to implement and use if effectively. I don’t know them. Still, it’s a nice thing to add to your tool chest.

Watch the full Matrix scene here: https://www.youtube.com/watch?v=z_KmNZNT5xw

Category Blog

What do you think?