Back

this page is mainly about C++ and algorithms.

re cur sion - n.  see recursion.

Euclid's recursive algorithm for finding the gcd of two integers

gcd(a,b){
if b = 0
   return a
else return gcd(a, a mod b)
}

For example,
gcd(30, 21)
gcd(21,9)
gcd(9,3)
gcd(3,0)
3

A C++ program using a recursive algorithm to detect a palindromic string (simplified)

#include<iostream>
#include<string>

using namespace std;

bool isPalindrome(string s);

int main(){

string userInput;
bool palTest;

cout << "Please enter a word or phrase: ";
getline(cin, userInput);

palTest = isPalindrome(userInput);

if (palTest == false)
cout << "\"" << userInput << "\"" << " is not a palindrome.\n";

else
cout << "\"" << userInput << "\"" << " is indeed a palindrome.\n";

return 0;
}

bool isPalindrome(string s)
/*Legal punctuation includes: spaces. Function is case-sensitive.*/
{
string first, last, space;
space = " ";
capA = "A";
capZ = "Z";
lowA = "a";
lowZ = "z";


first = s.substr(0,1);
last = s.substr(s.length()-1,1);

if ( ((first == space) || ((first >= capA) && (first <= capZ)) ||
   ((first >= lowA) && (first <= lowZ)) ) &&
    ((last == space) || ((last >= capA) && (last <= capZ)) ||
    ((first >= lowA) && (first <= lowZ))))

{
   if ((s == "") || (s.length() == 1))
     return true;

   if (first == space)
          return isPalindrome(s.substr(1,s.length()-1));

   if (last == space)
        return isPalindrome(s.substr(0,s.length()-1));

   if (first != last)
        return false;

   else if (first == last)
        return isPalindrome(s.substr(1,s.length()-2));
}

else
   return false;

}

C++ data structures are fun! Here is an example of a class definition for an abtract data type which uses a linked list to implement a data structure for storing very large integers. It utilizes the node class written by the author of our textbook.

#ifndef BIGNUM_H
#define BIGNUM_H
#include <cstdlib> // Provides size_t
#include "node1.h" // With value_type defined as an int

namespace dss03_HW3
{
class BigNum
{
public:
// CONSTRUCTORS and DESTRUCTOR
BigNum(const char str[] = "");
BigNum(const BigNum& source);
~BigNum( );

// MODIFICATION MEMBER FUNCTIONS
void operator =(const BigNum& source);

// CONSTANT MEMBER FUNCTIONS
size_t length( ) const {return len;}

// FRIEND FUNCTIONS
friend bool operator >(const BigNum& a, const BigNum& b);
friend bool operator ==(const BigNum& a, const BigNum& b);
friend BigNum operator +(const BigNum& a, const BigNum& b);
friend BigNum operator -(const BigNum& a, const BigNum& b);
friend istream& operator >>(istream& ins, BigNum& a);
friend ostream& operator <<(ostream& outs, const BigNum& a);
friend BigNum operator *(const BigNum& a, int digit);
friend BigNum operator *(const BigNum& a, const BigNum& b);

private:
main_savitch_5::node* digitlist_ptr;
size_t len;
};

// NONMEMBER FUNCTIONS for the BigNum class
bool operator !=(const BigNum& a, const BigNum& b);
bool operator <(const BigNum& a, const BigNum& b);
bool operator <=(const BigNum& a, const BigNum& b);
bool operator >=(const BigNum& a, const BigNum& b);
}

#endif

In my data structures class we had to write the implementation file for the above class. Multiplication functions were extra credit. :-)

An iterative algorithm for computing Fibonacci numbers:

fibonacci(n){
  if n = 0
    return 0;

  else {

    x = 0;
    y = 1;

    for(i = 1; i <= n; i++) {
      z = x + y;
      x = y;
      y = z;
    }

    return y;
  }
}

What is a Fibonacci number?

Assuming the first Fibonacci number (F0) is zero and the second (F1) is one, F(n+1) = F(n-1) + F(n-2). The first few Fibonacci numbers are: 0,1,1,2,3,5,8,13,21,54,75, etc. You can see that this sequence grows VERY fast. It grows so fast, in fact, that it is for all practical purposes impossible to compute any large Fibonacci number using a recursive algorithm. Iteration saves the day. :-)

Interesting fact: Fibonacci numbers may be computed directly by using the so-called Golden number: (1 + sqrt(5))/2 or ~1.618. The Golden ratio, 1.618:1, is the ratio of the sides of an aesthetically perfect rectangle. Golden rectangles can be seen all over the Parthenon in Greece, and the Golden number shows up many places in nature. You can compute the Golden number directly by finding the roots of the equation x^2 - x - 1 = 0. Use the quadratic formula

Back   Bio   Bloodninja   Calculus   C++   Food   Liquid Courage

Metal   Pai Gow   Photography   Power   Travel   Writings

disgorge@undertheblade.com