recursion.cpp

Code

/*
    recursion.cpp
    CIS 250
    Dave Klick
    2005-04-04

    Demonstrates a number of recursive functions.
*/

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <conio.h>

using std::cout;
using std::cin;
using std::endl;
using std::setw;

char pause() { return getche(); }
char cont() { cout << "Press any key to continue "; return pause(); }
long fact(long);
void dofact();
long fib(long);
void dofib();
bool isPrime(long);
bool factorinrange(long, long);
void doprime();
void dogcd();
int gcd(int, int);
void dogcd2();
int gcd2(int, int);
void dotoh();
void toh(int, int, int);
void docount();
void count(int);
void doprint();
void print(char*);

int main(void) {
    char c;
    do {
        system("cls");
        cout << "Menu\n\n1. factorial\n\n2. fibonacci\n\n"
            "3. prime numbers\n\n4. greatest common divisor\n\n"
            "5. greatest common divisor II\n\n6. towers of Hanoi\n\n"
            "7. countdown\n\n8. display string\n\n"
            "9. exit\n\nYour choice: ";
        c = pause();
        cout << endl;
        switch (c) {
            case '1': dofact(); break;
            case '2': dofib(); break;
            case '3': doprime(); break;
            case '4': dogcd(); break;
            case '5': dogcd2(); break;
            case '6': dotoh(); break;
            case '7': docount(); break;
            case '8': doprint(); break;
            case '9': break;
            default: cout << "Invalid option - "; cont();
        }
    } while (c != '9');
    return 0;
}

void dofact() {
    int i;
    cout << "Factorials\n N        N!\n-- ---------\n";
    for (i=0; i<11; i++) {
        cout << setw(2) << i << setw(10) << fact(i) << "\n";
    }
    cont();
    return;
}

void dofib() {
    int i;
    cout << "Fibonacci Numbers\n N    fib(N)\n-- ---------\n";
    for (i=0; i<11; i++) {
        cout << setw(2) << i << setw(10) << fib(i) << "\n";
    }
    cont();
    return;
}

void doprime() {
    int i;
    cout << "Primes    \n N  Prime\n--  ------\n";
    for (i=1; i<37; i+=2) {
        cout << setw(2) << i << "  " << (isPrime(i)?"Yes":"No") << "\n";
    }
    cont();
    return;
}

void dogcd() {
    int a, b;
    cout << "  a    b  gcd\n---  ---  ---\n";
    a = 23; b = 86;
    cout << setw(3) << a << "  " << setw(3) << b
        << "  " << setw(3) << gcd(a,b) << endl;
    a = 105; b = 75;
    cout << setw(3) << a << "  " << setw(3) << b
        << "  " << setw(3) << gcd(a,b) << endl;
    a = 156; b = 204;
    cout << setw(3) << a << "  " << setw(3) << b
        << "  " << setw(3) << gcd(a,b) << endl;
    a = 79; b = 39;
    cout << setw(3) << a << "  " << setw(3) << b
        << "  " << setw(3) << gcd(a,b) << endl;

    cont();
    return;
}

void dogcd2() {
    int a, b;
    cout << "  a    b  gcd\n---  ---  ---\n";
    a = 23; b = 86;
    cout << setw(3) << a << "  " << setw(3) << b
        << "  " << setw(3) << gcd2(a,b) << endl;
    a = 105; b = 75;
    cout << setw(3) << a << "  " << setw(3) << b
        << "  " << setw(3) << gcd2(a,b) << endl;
    a = 156; b = 204;
    cout << setw(3) << a << "  " << setw(3) << b
        << "  " << setw(3) << gcd2(a,b) << endl;
    a = 79; b = 39;
    cout << setw(3) << a << "  " << setw(3) << b
        << "  " << setw(3) << gcd2(a,b) << endl;

    cont();
    return;
}

void dotoh() {
    cout << "Towers of Hanoi: moving 4 disks from peg 1 to peg 3" << endl;
    toh(4, 1, 3);
    cont();
    return;
}

void docount() {
    cout << "Countdown from 10" << endl;
    count(10);
    cont();
    return;
}

void doprint() {
    cout << "Displaying recursively: Hello, world!" << endl;
    print("Hello, world!");
    cout << endl;
    cont();
    return;
}

long fact(long n) {
    if (n<0) return -1;
    if (n==0) return 1;
    else return n * fact(n-1);
}

void toh(int n, int pf, int pt) {
    if (n==0) return;
    if (n==1) cout << pf << "->" << pt << endl;
    else {
        toh(n-1, pf, 6-pf-pt);
        cout << pf << "->" << pt << endl;
        toh(n-1, 6-pf-pt, pt);
    }
}

void count(int n) {
    if (n<=0) cout << "Boom!\a\a\a\a\a" << endl;
    else {
        cout << n << ".. ";
        count(n-1);
    }
}

int gcd(int x, int y) {
    if (x<y) return gcd(y, x);
    if (y<=0) return -1;
    if (x%y==0) return y;
    else return gcd(y, x%y);
}

int gcd2(int x, int y) {
    if (y<=0) return -1;
    if (x==y) return x;
    if (x>y) return gcd2(x-y, y);
    return gcd2(x, y-x);
}

void print(char* s) {
    if (*s) {
        cout << s[0];
        print(s+1);
    }
}

long fib(long n) {
    if (n<0) return -1;
    if (n==0 || n==1) return n;
    return fib(n-1) + fib(n-2);
}

bool isPrime(long n) {
    if (n==1) return false;
    return (n>1) && !factorinrange(2,n);
}

bool factorinrange(long r, long n) {
    if (r>n) return false;
    else if (n%r==0) return true;
    else return factorinrange(r+1, n);
}