Recursion in Computer Science

Recursion, though important is frequently overlooked by programmers who do not understand its potential and place in algorithm design. It allows the expression of some problems in a very elegant and succinct manner, problems such as the famous Fibonacci number sequence are better understood and written with the aid of recursion. We will go through a few algorithms that employ It in an attempt to explain its function in a clear and concise manner.

I will be using python in this post because its a scripting language and therefore there is no need to recompile while testing my code. If you do not have python on you machine you can get it here python;  python IDE .

“A picture is worth a thousand words” is certainly true for this photo, in order for recursion to work there has to be at least one base case. The algorithm can have multiple base cases each of which is responsible for a particular state in which the algorithm may be in at each step. So lets look at our first example of a simple recursive function written in python.

Counting backwards from 10 to 0

def countDescending(num):
     print num
     if num == 0: return
     countDescending(num - 1)

Analysis

  1. The countDescending accepts a number as input then prints that number
  2. Base case: When num = 0 return from the function.
  3. Recursive step:The function calls itself with the input being reduced by 1

NB* All recursive solutions the initial problem must be one that can be broken down into simpler  problems, which eventually leads to the base case. Also to note, each function  call along  with scoped non-static variables are held on the stack until the base case is reached at which point the stack is unwound and the resources released.

Fibonacci Number

def fib(num):
    if num < 2:return num
    if num > 0 :return fib(num-1) + fib(num-2)

Analysis

Fibonacci Number sequence: 0, 1, 1, 2, 3, 5, 8
Recursive formula: \displaystyle f_{n} = \sum_{n=1}^{8} (n-1)+(n-2)
Base case: If input is less than 2 return the original input.
Recursive step: If input greater than 0 call fib with number – 1 and number – 2
Recursion Tree:

A recursion tree allows us to gain insight into the workings of a recursive algorithm, the above diagram shows the recursion tree for the Fibonacci number  8. From it we note that there is lot of repetition in calculation, this could be avoided with the use momoization which we will discuss in a future article.

Advertisements

How to clear the Immediate window in Microsoft Visual Studio

If you have used Visual Studio x for any length of time you would have become familiar with the immediate window, this window allows you to quickly evaluate expressions when a break point is hit. You would have equally been frustrated with having to right click in the window to then clicking clear allHere is a neat trick that will allow you to clear the command window, just type >cls  then hit return and surprise the window will be cleared ;-).

TOPCODER Practice Room Solution – 250 Problem


using System.Text.RegularExpressions;
using System;

public class HowEasy
{
public int pointVal(String param)
 {
 Regex reg = new Regex(@"\b[a-zA-Z]+\b(?![0-9]|[.]{2,})", RegexOptions.IgnoreCase);
 MatchCollection matches = reg.Matches(param);

int rtotal = 0, avg = 0;

foreach (Match match in matches)
 rtotal += match.Length;

 avg = rtotal / matches.Count;

 if(avg < 3)
 {
 return 250;
 }else if(avg == 4 | avg == 5)
 {
 return 500;
 }else if(avg >= 6)
 {
 return 1000;
 }
 return 0;
 }
}

This is an example of how to use word boundaries, negative lookahead and quantifier repetition. [Regex Tut]

Setting Up Visual Studio 10 for MASM32 Programming

If you are like me and want the comfort and support that Microsoft’s Visual Studio 10 provides, then you will defiantly want that support in your MASM programming tasks. Visual studio makes this quite easy, with a couple of project property changes you will be on your way to MASM programming bliss.

Steps

  1. Create new Visual C++ Empty Project
  2. Right click on the newly created project and select Build Customizations; select masm option, press ok then save the project.
  3. Go to project properties and select linker->system then change subsystem to Windows (/SUBSYSTEM:CONSOLE)
  4. Download and install masm32 libraries then add them to your linker settings.
  5. Go to linker->Advanced and change Entry Point to main [this is what the linker will look for when mapping the entry point for your app.]
  6. Go to Linker->Input  and add masm32.lib to Additional Dependencies.
  7. Go to Microsoft Macro Assembler->General and add the masm32 libraries.
  8. Download and paste usertype.dat into C:\Program Files (x86)\Microsoft Visual Studio 10.0\Common7\IDE
  9. Go to Visual Studio Options->Text Editor->File Extensions: Type asm in the extension box then select Microsoft Visual  C++ from the list.
  10. Right click on project and select Add->New Item: Select Text File and save with *.asm
  11. Create, run and enjoy your code 🙂

In a future post I will show how to turn this project into a Visual Studio project template.