Recursion

Previous Topic    Course Outline

Recursion might be one of hardest concept to grasp for a newbie but once you get the hang out of it, you'll find it really cool!

When you see a function that is calling itself, that's a recursion. So basically, you're performing something onto a subject over and over again until it becomes what you desire.

An example would be dropping the first and last letters of a word until its length becomes 1 (for odd-length strings) or 2 (for even-length strings) which will give you the word's middle letter(s).

theComSciGeek
heComSciGee
eComSciGe
ComSciG
omSci
mSc
S

One important thing in recursion is you should know where to stop. That's your basis. In this example, we stop if the length of the string is already less than or equal to 2.

Another example would be determining if a number is a multiple of 2.

1 2 3 4 5 6 7 8 9

int isMultipleOfTwo(int num) { if (num == 2) { return 1; } if (num < 2) { return 0; } return isMultipleOfTwo(num/2); }

I know that these are not so clever examples of recursion but these are pretty easy to grasp. Just remember this rule thumb: when you feel like you're doing the same thing over and over again to a certain subject, that's when recursion comes in. 

Most (if not all) recursions can be implemented using loop(s). It's just that recursions are awesome and most of the time, if not always, less expensive than loops with regards to both space and time complexity.


Previous Topic    Course Outline