[cxS]

Recursion Guide for Dummies
Written by cxS - 2013

What is it?

• Essentially, recursion is the process of taking a larger problem, and being able to break it into a set of smaller problems to solve, in attempt at eventually solving the bigger problem. If you have ever heard of the term binary tree in programming, at recursion from a glance, you can quite easily relate the paradigm of a recursive algorithm to a binary tree.

Why use it?

• I get lots of people who just don't use recursion. Here are a few reasons why:
  
  • - They think it is too difficult to understand and implement
    - They don't know how to use it to their advantage
    - They don't recognize an opportunity where recursion may be a better alternative
    - They like iterative methods better, or have simply just become too accustomed to iterative thinking
  
  There are some languages where recursion is a bit more impractical. In Javascript for instance, recursion can be a burden, as a resource hog. For most languages, it can be a good thing, and here are some of my main reasons why:
  
  • - Iterative methods can become quite complex for the simplicity that recursive methods can offer alternatively
    - They can make code look cleaner, and shorter!

Where to use it?

• This question poses a variety of debatable answers. In some cases it boils down to personal preference, and in others, recursion may be your only choice, unless you want to end up writing a seriously long, convoluted, and complex bible of code to do what recursion can do for you with ease.
  
  To determine whether recursion is an option in a particular case, there is some algebraic proof involved, which yields the result for number of recursive steps and the expected running time of the recursive algorithm itself you are using...
  
  For reasons of encouragement however, I'm not going to go that far in depth though as this would probably be enough in itself to deter a few people from taking advantage of recursion in their programming ventures.
  
  Lets move away from this philosophical and introductory stuff though shall we?

What does it look like?

• When you think of recursion you need to be able to think about how to break apart a larger problem into smaller sub-problems in order to solve individually, allowing us to solve the bigger problem eventually.
  
  The most important thing to think about is when we're done solving these smaller sub-problems. Forget about thinking in terms of iterative methods... This may be very difficult at first because traditional iterative methods follow a more straightforward path of logic.
  
  With iterative methods, it is easier to visualize when we are finished, and have a good result. Recursion is a bit different, and the visualization of the process itself, looks more widespread than linear.
  
  If you do not know when to stop your recursive method, then you could end up creating an infinite recursive binary tree of instructions for many levels, and this you do not want.
  
  Take for instance a recursive method below that I wrote, which can check if an input string is a palindrome:
  
  Code:

  private static bool IsPallindrome(string s, int lowerIndex, int upperIndex)
{
    if (upperIndex <= lowerIndex)
    {
        return true;
    }
    if (s[lowerIndex] != s[upperIndex])
    {
        return false;
    }
    return IsPallindrome(s, ++lowerIndex, --upperIndex);
}
  
  This code works by recursively comparing the lower and upper index's from the original string, and eventually converge until they meet up in the center of the string. When we get to the center with both indexes as they converge, we should know that all of the characters of the string have been checked, so there is no need to evaluate any further; return true. If a mismatch is found, this would also break the recursive looping because we're directly returning false under that circumstance, and not the value returned from solving another sub-problem of the current problem; calling itself again.
  
  Without the first couple if statements, you could imagine this index converging, as 2 people walking towards each other, continuing along their paths until they eventually pass each other. What was meant to happen however, for whatever reason, is that they were supposed to stop when they reached each other, not walk past one another. (Perhaps for a chat?)
  
  We can also use it to calculate the result of a certain input numerical value, raised to an exponent, as shown in my own code below:
  
  Code:

  private static decimal Power(decimal num, decimal exp)
{
    if (exp < 1)
    {
        return 1;
    }
    else if (exp == 1)
    {
        return num;
    }
    else
    {
        return num * Power(num, exp - 1);
    }
}

How does recursion work?

• Recursion works by working on portions of the pie so to speak, in a process of solving then collecting. I don't really know how else to explain recursion visually.
  
  If any of you have seen the movie "Pay it forward", this would be a great example of the concept of recursion. One of the ideas portrayed in this film, how fast help can spread if everybody works according to a certain system. Help 3 people, and tell each of those 3 people to help another 3 people each. Eventually, you've got a pretty large collection of helpers. If they each work towards a certain goal, it's the principle of solving minor problems, but perhaps the larger problem is eventually becoming more solved because it had been broken up into multiple sub-problems in such a way that we can eventually solve the entire puzzle.

Recursion vs. Iteration?

• Recursively:
  
  Code:

  private static int Recur(int steps)
{
    if (steps == 0)
        return 2;
    return 2 * Recur(--steps);
}
  
  
  Code:

  for (int i = 0; i < 10; i++)
{
    Console.WriteLine(Recur(i));
}
  
  Now iteratively:
  
  Code:

  private static int Iter(int steps)
{
    // Avoiding Math.Pow() here to keep things fair
    int x = 2;
    for (int i = 0; i < steps; i++)
    {
        x *= 2;
    }
    return x;
}
  
  
  Code:

  for (int i = 0; i < 10; i++)
{
    Console.WriteLine(Iter(i));
}
  
  Now benchmarking these 2 methods for a count of 1,000,000 runs and a final average of 10 averages of those 1,000,000 runs each... We can see that the results are pretty much the same for this test:
  
  
  Code:

  (Benchmark Test... 10 averages of 100000 runs)

# Iter()
> [Average 1/10] Complete - 13.84371 ticks
> [Average 2/10] Complete - 13.54264 ticks
> [Average 3/10] Complete - 14.13739 ticks
> [Average 4/10] Complete - 13.86204 ticks
> [Average 5/10] Complete - 13.7073 ticks
> [Average 6/10] Complete - 13.66891 ticks
> [Average 7/10] Complete - 13.79626 ticks
> [Average 8/10] Complete - 13.90589 ticks
> [Average 9/10] Complete - 13.87798 ticks
> [Average 10/10] Complete - 13.82147 ticks
# Result: 13.816359 ticks

(Benchmark Test... 10 averages of 100000 runs)

# Recur()
> [Average 1/10] Complete - 13.34126 ticks
> [Average 2/10] Complete - 13.21534 ticks
> [Average 3/10] Complete - 13.00516 ticks
> [Average 4/10] Complete - 13.57818 ticks
> [Average 5/10] Complete - 14.45852 ticks
> [Average 6/10] Complete - 14.36396 ticks
> [Average 7/10] Complete - 14.3355 ticks
> [Average 8/10] Complete - 14.51135 ticks
> [Average 9/10] Complete - 14.49346 ticks
> [Average 10/10] Complete - 14.47885 ticks
# Result: 13.978158 ticks
  
  Other uses for recursion involve generating the Fibonacci sequence, Fractals, the Merge Sort algorithm, etc...
  
  I would highly advise that you experiment with recursion though.

[๖ۣۣۜۜFear]

Very good guide in the name of Syndicate, I look forward to seeing more CS tutorials/guides from you.