This file contains (part of) the code from "Algorithms in C, Third Edition,
Parts 1-4," by Robert Sedgewick, and is covered under the copyright
and warranty notices in that book. Permission is granted for this
code to be used for educational purposes in association with the text,
and for other uses not covered by copyright laws, provided that
the following notice is included with the code:

 	"This code is from "Algorithms in C, Third Edition,"
	by Robert Sedgewick, Addison Wesley Longman, 1998."

Commercial uses of this code require the explicit written
permission of the publisher. Send your request for permission,
stating clearly what code you would like to use, and in what
specific way, to: aw.cse@aw.com

CHAPTER 5. Recursion and Trees
-----
int factorial(int N)
  {
    if (N == 0) return 1;
    return N*factorial(N-1);
  }  
-----
int puzzle(int N)
  {
    if (N == 1) return 1;
    if (N % 2 == 0)
         return puzzle(N/2);
    else return puzzle(3*N+1);
  }  
-----
int gcd(int m, int n)
  {
    if (n == 0) return m;
    return gcd(n, m % n);
  }  
-----
char *a; int i;
int eval()
  { int x = 0;
    while (a[i] == ' ') i++;
    if (a[i] == '+')
      { i++; return eval() + eval(); }
    if (a[i] == '*')
      { i++; return eval() * eval(); }
    while ((a[i] >= '0') && (a[i] <= '9')) 
      x = 10*x + (a[i++]-'0'); 
    return x;
  }
-----
int count(link x)
  { 
    if (x == NULL) return 0;
    return 1 + count(x->next); 
  }
void traverse(link h, void (*visit)(link))
  { 
    if (h == NULL) return;
    (*visit)(h); 
    traverse(h->next, visit);
  }
void traverseR(link h, void (*visit)(link))
  { 
    if (h == NULL) return;
    traverseR(h->next, visit);
    (*visit)(h); 
  }
link delete(link x, Item v)
  { 
    if (x == NULL) return NULL;
    if (eq(x->item, v))
      { link t = x->next; free(x); return t; }
    x->next = delete(x->next, v);
    return x;
  }
-----
Item max(Item a[], int l, int r)
  { Item u, v; int m = (l+r)/2; 
    if (l == r) return a[l];
    u = max(a, l, m);
    v = max(a, m+1, r);
    if (u > v) return u; else return v;
  }
-----
void hanoi(int N, int d)
  {
    if (N == 0) return;
    hanoi(N-1, -d);
    shift(N, d);    
    hanoi(N-1, -d);
  }  
-----
rule(int l, int r, int h)
  { int m = (l+r)/2;
    if (h > 0)
      { 
        rule(l, m, h-1);
        mark(m, h);
        rule(m, r, h-1);
      }
  }
-----
rule(int l, int r, int h)
  { 
    int i, j, t;
    for (t = 1, j = 1; t <= h; j += j, t++)
      for (i = 0; l+j+i <= r; i += j+j)
        mark(l+j+i, t);
  }
-----
int F(int i)
  { 
    if (i < 1) return 0;
    if (i == 1) return 1;
    return F(i-1) + F(i-2);
  }
-----
int F(int i)
  { int t;
    if (knownF[i] != unknown) return knownF[i];
    if (i == 0) t = 0;
    if (i == 1) t = 1;
    if (i > 1) t = F(i-1) + F(i-2);
    return knownF[i] = t; 
  }
-----
int knap(int cap)
  { int i, space, max, t;
    for (i = 0, max = 0; i < N; i++)
      if ((space = cap-items[i].size) >= 0)
        if ((t = knap(space) + items[i].val) > max) 
          max = t;
    return max;     
  }
-----
int knap(int M)
  { int i, space, max, maxi, t;
    if (maxKnown[M] != unknown) return maxKnown[M];
    for (i = 0, max = 0; i < N; i++)
      if ((space = M-items[i].size) >= 0)
        if ((t = knap(space) + items[i].val) > max)
          { max = t; maxi = i; }
    maxKnown[M] = max; itemKnown[M] = items[maxi];
    return max;     
  }
-----
void traverse(link h, void (*visit)(link))
  { 
    if (h == NULL) return;
    (*visit)(h); 
    traverse(h->l, visit);
    traverse(h->r, visit);
  }
-----
void traverse(link h, void (*visit)(link))
  {
    STACKinit(max); STACKpush(h);
    while (!STACKempty())
      {
        (*visit)(h = STACKpop());
        if (h->r != NULL) STACKpush(h->r); 
        if (h->l != NULL) STACKpush(h->l); 
      }
  }
-----
void traverse(link h, void (*visit)(link))
  {
    QUEUEinit(max); QUEUEput(h);
    while (!QUEUEempty())
      {
        (*visit)(h = QUEUEget());
        if (h->l != NULL) QUEUEput(h->l); 
        if (h->r != NULL) QUEUEput(h->r); 
      }
  }
-----
int count(link h)
  { 
    if (h == NULL) return 0;
    return count(h->l) + count(h->r) + 1;
  }
int height(link h)
  { int u, v;
    if (h == NULL) return -1;
    u = height(h->l); v = height(h->r);
    if (u > v) return u+1; else return v+1;
  }
-----
void printnode(char c, int h)
  { int i;
    for (i = 0; i < h; i++) printf("  ");
    printf("%c\n", c);
  }
void show(link x, int h)
  { 
    if (x == NULL) { printnode("*", h); return; }
    show(x->r, h+1);    
    printnode(x->item, h);
    show(x->l, h+1);    
  }
-----
typedef struct node *link;
struct node { Item item; link l, r };
link NEW(Item item, link l, link r)
  { link x = malloc(sizeof *x); 
    x->item = item; x->l = l; x->r = r;
    return x;
  }
link max(Item a[], int l, int r)
  { int m = (l+r)/2; Item u, v;
    link x = NEW(a[m], NULL, NULL);
    if (l == r) return x;
    x->l = max(a, l, m);
    x->r = max(a, m+1, r);
    u = x->l->item; v = x->r->item;
    if (u > v) 
      x->item = u; else x->item = v;
    return x;
  }
-----
char *a; int i;
typedef struct Tnode* link;
struct Tnode { char token; link l, r; };
link NEW(char token, link l, link r)
  { link x = malloc(sizeof *x); 
    x->token = token; x->l = l; x->r = r;
    return x;
  }
link parse()
  { char t = a[i++];
    link x = NEW(t, NULL, NULL);
    if ((t == '+') || (t == '*'))
      { x->l = parse(); x->r = parse(); }
    return x;
  }
-----
void traverse(int k, void (*visit)(int))
  { link t;
    (*visit)(k); visited[k] = 1;
    for (t = adj[k]; t != NULL; t = t->next)
      if (!visited[t->v]) traverse(t->v, visit);
  }
-----
void traverse(int k, void (*visit)(int))
  { link t;
    QUEUEinit(V); QUEUEput(k);
    while (!QUEUEempty())
      if (visited[k = QUEUEget()] == 0)
        {
          (*visit)(k); visited[k] = 1;
          for (t = adj[k]; t != NULL; t = t->next)
            if (visited[t->v] == 0) QUEUEput(t->v);
        }
  }
-----

----------