A Simplified Guide to Understanding Recursion

For many beginning computer science students, the idea of recursion is difficult to grasp. I wager that some more experienced computer science students or even some seasoned developers out of college and already out in the field don't really grasp the idea of recursion. As an f.y.i., I use "function" and "method" interchangeably to mean the same thing (it depends on which language you're most comfy with).

First of all, all recursive functions have what is known as a "base case". A base case is the "state" which you want to get to with the recursive function. If you haven't met the base case yet, you take steps to get to that base case.

As an example to illustrate this concept, let's look at the factorial function. For a technical definition of a factorial, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. In case you forgot about 0! (the ! sign is the formal operator for the factorial), 0! is equal to 1 (so we will just forget about it). Now, let's use 5! as our example. If we were to multiply this out manually, we have

5! = 5 * 4 * 3 * 2 * 1 = 120

Now that we know this, let's build a recursive function to do this. In this demo, I will use C# as the programming language, but it's the same idea in Java and C++.

public int recursiveFactorial(int base, int multiplier) {
     //this is our base case
     if (multiplier == 1) {
         return base;
     }
     else {
         //if we haven't met our base case yet, we take steps to get to that base case
         base = base * multiplier;
         return recursiveFactorial(base, (multiplier - 1));
}

Now let's look at what this function does. It first takes in 2 integers as input, base and multiplier. Base is the number we start out with (in this case, 5), and multiplier is the number we will multiply base by if we haven't met our base case (multiplier starts out as base - 1 to fit the definition of the factorial). The base case here is to get multiplier = 1. So now, let's run our function and see how the recursion works.

First, we will call

recursiveFactorial(5, 4);

Now here, we check: is 4 equal to 1? No, it is not, so the else part of our recursive function activates and we simplify things to get closer to our base case by calling the function again with 20 as our base input variable and (4-1) as our multiplier input variable.

recursiveFactorial(20, 3);

Now we check again: is 3 equal to 1? No, it is not, so the else part of our recursive function activates again (and we multiply base times multiplier) to get closer to our base case.

recursiveFactorial(60, 2);

Are we starting to get the picture yet? Now here, we check: is 2 equal to 1? No, it is not, so the else part of our recursive function activates yet again and things are simplified even more (by multiplying base times multiplier again) to get ever closer to our base case.

recursiveFactorial(120, 1);

We check again: is 1 equal 1? Yes, we have finally met our base case, so we just end things by returning base. From here, the value "bubbles up" to the top "level" (where we first called the recursiveFactorial function).

If you've ever heard the term "stack overflow", it comes from this idea of recursion. With a stack overflow, a recursive function is called so many times that the computer doesn't have enough memory available to handle the recursion, so the computer crashes.

So does this guide help you to grasp the idea of recursion? If you are a seasoned developer, can I improve this guide (or give better examples)? Please let me know in the comment box below.

While you're learning about recursion, why not try some delicious Mystic Monk Coffee? Mystic Monk Coffee (use this link or click on the picture below to access the store and purchase) is what you really need when it comes to coffee. Trust me, it's good coffee (in most instances, much better than Starbucks coffee) and you won't regret buying some (just keep it away from your computer keyboard or laptop/tablet). If you like tea more than coffee, they also offer tea. If you have a Keurig machine, the monks also have k-cups for purchase as well (known as "monk shots") Using the link (or picture below) to buy the coffee (or tea) helps the monks out and helps me with my endeavors as well. The coffee (or tea) also makes for great gifts for friends and family as well.

While we are waiting for updates to my windows phone apps (trust me, I'm working on them), if you want to go ahead and get my apps now, please use the following links:

BSA Eagle Tracker download: http://bit.ly/Mm1Upo
Mobile Media Manager (paid version) download: http://bit.ly/y3rf6V
Mobile Media Manager (free version) download: http://bit.ly/xGCsWE
CodeProject

Signup for 30 Days to Launch Contest: Only 4 Days Left

Update (6/4/2012): Entry for the contest is now closed.

Update (6/1/2012: Only 2 days left now)

If you haven't noticed it at all either because you were busy with something else, working on final exams, or living under a rock, Microsoft is offering the 30 Days to Launch Contest for any developer out there.

The goal of the 30 Days to Launch Contest is to learn how to develop a Windows Phone app (or if you already have some knowledge of Windows Phone, a chance to increase that knowledge) and produce one in 30 days. After that 30 days for submitting your apps are up, you have an additional 15 days to make publication decisions for each of them. Each person gets 1 entry into the contest, so if you submit more than 1 program to the marketplace within that time frame, choose your contest entry wisely. At the end, all entries will be judged by popular vote from now until August 13.

If you need the Windows Phone SDK, you can just click on the picture below to download it.

The prizes are:
   Four (4) Grand Prizes. Each winner will receive a Prize Package consisting of a La-Z-Boy© recliner and a Lenovo IdeaPad 300 Ultrabook™. Approximate Retail Value (ARV) $ 3,000 per prize package.

Please note that you must have an apphub account to participate in this contest. If you don't have one, students can get an account free through Dreamspark. If you aren't a student, you can still get an apphub account by following these steps:

• First, sign up for www.30tolaunch.com using a Windows Live ID
• Second, spread the word via Social Media in one of the following ways:
  • Like the Microsoft User Community Facebook page: http://on.fb.me/Aho2an
  • OR Tweet about 30 to Launch by telling us about your participation. For your tweet to qualify, you must reference the tag #30tolaunch AND include the following in the body of your tweet: I am participating in 30 to Launch to build a Windows Phone app! Rules: http://aka.ms/f1i1lr. We reserve the right to remove any inappropriate tweets.
• Third, provide a short description of the app you plan to create and submit through the online form by clicking on the I’m Done button for Week 2 for your 30 to Launch Windows Phone app on the My 30 to Launch Idea page.

Only entries for new apps (not updates to existing apps) are accepted for entries. You must also be 18 years of age or older to enter.

WHAT CONSTITUTES AN ELIGIBLE ENTRY?

To be eligible for judging an entry must meet the following content / technical requirements:

• Your application must be coded and submitted as a Windows Phone Application within 30 days of your sign-up date and must be published to the Windows Phone Marketplace no earlier than 7 days and within 45 days of your sign-up date. Tools for Windows Phone development which can be downloaded here include:
  • Visual Studio 2010 Express for Windows Phone
  • Windows Phone Development Tools
  • Express Blend for Windows Phone
  • Windows Phone Emulator
• You must complete the Voting requirement between July 30, 2012 August 13, 2012 to vote for ONE 30 to Launch app published during the campaign. You cannot vote for your own app.

In addition:

• your entry must be your own original work; and
• your entry should be published to the marketplace on or after 7 days following your sign up date. Your app should not be something previously submitted to the Windows Phone Marketplace prior to this contest; and
• you must have obtained any and all consents, approvals or licenses required for you to submit your entry; and
• your entry may not include any third party trademarks (logos, names) or copyrighted materials (music, images, video, recognizable people) unless you have obtained permission to use the materials. You may include Microsoft trademarks, logos, and designs, for which Microsoft grants you a limited license to use for the sole purposes of submitting an entry into this Contest.

Entries may NOT contain, as determined by us, in our sole and absolute discretion, any content that:

• is sexually explicit, unnecessarily violent or derogatory of any ethnic, racial, gender, religious, professional or age group; profane or pornographic;
• promotes alcohol, illegal drugs, tobacco, firearms/weapons (or the use of any of the foregoing) or a particular political agenda;
• is obscene or offensive;
• defames, misrepresents or contains disparaging remarks about other people or companies;
• communicates messages or images inconsistent with the positive images and/or good will to which we wish to associate; and/or violates any law;

We reserve the right to reject any entry, in our sole and absolute discretion, that we determine does not meet the above criteria.

Apps will be judged on the following basis:

• 25.00% - Does the app utilize the live tile or secondary tile feature? (does not apply to game applications)
• 25.00% - Does the app have market potential given current mobile application trends?
• 25.00% - Is the app innovative and original?
• 25.00%- Does the app use additional Windows Phone 7.5 capabilities such as cloud-enablement through Windows Azure*, Background Agents, Background Audio, Pictures Hub integration, Music & Video Hub integration etc.
  • *Cloud-enabling the application using Microsoft Windows Azure includes scenarios such as:
    • Use “push notifications” to send updates
    • Manage gamer identity using their Facebook, Google, LiveID, etc.
    • Push video or images using Windows Azure CDN
    • Add leader boards, social interaction, shared landscapes, player location and movement
    • Send Line-of-business data using OData standards

The last day to sign up is June 3, 2012.

For more information, please see the contest rules at http://www.30tolaunch.com/WindowsPhone/Contest/OfficialRules. If you have any questions, feel free to ask them in the comment box below or e-mail me at catholictechgeek@gmail.com. You can also ask me on twitter (twitter username is @rctechgeek). Feel free to subscribe to my rss feed as well.

If you need some coffee to help get you going in the morning to give you the inspiration to accomplish your app or to help you stay awake while working on your app, try some Mystic Monk Coffee (use this link to access the store and purchase). Trust me, it's good coffee (in many instances, better than Starbucks coffee) and you won't regret buying some. For the summer they are also offering Iced Coffee as well. If you like tea with your coding more than coffee, they also offer tea (use the same link above).

Feel free to try out my apps for Windows Phone: Mobile Media Manager, a media player app I made which has some features which (I feel) are missing from the system zune player, and BSA Eagle Tracker, an app that boy scouts can use to track their progress to Eagle Scout (when the scout handbook isn't always handy). A new version of BSA Eagle Tracker will be out in the marketplace in a few days once it passes certification.

BSA Eagle Tracker download: http://bit.ly/Mm1Upo
Mobile Media Manager (paid version) download: http://bit.ly/y3rf6V
Mobile Media Manager (free version) download: http://bit.ly/xGCsWE