Please please, stop with factorials!
A look at the beauty of recursion, with an analogy and yes, without factorial.
It seems that every single tutorial ever written on recursion, uses the Factorial algorithm as an example. As a newbie, it can be hard to understand what recursion is when you only see it in one way. In this article, I will show how to write 13 basic algorithms (the ones used in the basic 13 at Coding Dojo), which are usually solved with loop iteration, using recursion. This really helped me understand recursion better. Plus, I’ll try my hand at an analogy and will give an example where just about everyone would agree that you”ll need to use recursion. Hello flatten. And yeah, goodbye factorial, at least for now.
A few disclaimers: As I understand, Functional programming is an interesting topic, but it’s also a complex one. Many programmers have feelings about it, some good and some bad. Being that my experience is limited, I will not get into FP, (there are many concepts involved, such as state, mutability, tail call optimization, concurrency and side effects.) Using FP in the real world requires many considerations most of which I am not well versed enough, so I will therefore stick to the thought process and the stylistic beauty of the recursive programming paradigm. There is definitely a learning curve, but understanding how to recursively write algorithms, will really broaden you understanding of programming (it did for me, at least), and yeah, its really fun too!
Remember: always make sure you have a base case/stop case (condition), or you will get a “maximum call stack reached” error.
First a few of the basic 13, then an analogy (just figured out how to link to a paragraph :).
1. Get 1 to 255
Write a function that returns an array with all the numbers from 1 to 255. You may use the push() function for this exercise.
2. Get even 1-10
Write a function that would get the sum of all the even numbers from 1 to 10. You may use a modulus operator for this exercise.
3. Replace negative numbers with 0 (or with anything of your choice)
Write a function that would change any negative value in an array to 0.
(More of the basic 13 are on their way….)
The No-Pen analogy
Here’s a little analogy that I thunk up (no pun intended). It’s far from perfect and probably a bit silly, but it helped me .
It’s 1998 and you call your friend Jen to ask her for Mike’s number. She quickly finds her contact book a proceeds to rattle the number off to you. Jen is super organized, she always has her book handy, but you, not so much. You quickly realize that you dont have a pen to write dont Mike’s number so you tell Jen to hold up while you scream to Sam in the next room to please remember this number for you. Sam repeats the number over and over to keep it fresh, and when you hang up wit Jen, you ask Sam to repeat the number back to you and you proceed to call Mike. I exhausted juts thinking about it.
Fast forward to 2017. We’re all using smartphones, and the no-pen problem is history.
Say I call a company, and I want them to give me a number to another department, (yes, I can just have them transfer me, or) I can simply click “add call”, punch in the number and make the new phone call from within my original call. No pen needed, and no Sam needed.
Sam (the person remembering my number) is like the “i” variable in a for loop. It’s an external container keeping track of some data for me. Well, what if I can just get rid of Sam (we love you Sam, but you gotta go) and keep track of our own data by just simply passing it into the new call? Pretty cool, no? (I think the words state, and mutability would go somewhere in this paragraph but I’m not quite there yet. ;)
Flatten a nested array
I promised I would show you an algorithm that could really benefit a lot from recursion. Here is is. It involves pushing the contents of an array that has many nested arrays inside of it, into a new array and in the correct order. Using a for loop (without some kind of built in function) would get super messy.
var flattened = [];
function flatten(a, i) {
if(a.length > i) {
if(Array.isArray(a[i]))
flatten(a[i], 0);
else
flattened.push(a[i]);
flatten(a, i + 1);
}
}
flatten([[0, 1], [2, 3], [4, 5]], 0);
console.log(flattened);//courtesy of stackOverflow Adam https://stackoverflow.com/users/4491066/adam
Every morning at Coding Dojo, we spend an hour on algorithms. This article was inspired by last weeks recursive algorithms. I hoped that by writing about the topic, it would help solidify my understanding. It definitely helped me, and I hope it helped you as well.
You can follow my coding journey here.
Thanks for reading!
