CS 1723 students.  Additional comments about the final:

Most of the remarks below show recursive solutions that were
not provided in the answer sheet.  Some of these answers I
adapted from answers by Cochetti, Gibson, Hons, and Savage.  (Thanks.
It looks like some of you are really getting into recursion.)
All the programs below ran as shown, though I did some cutting and pasteing.

PROBLEM 1:
four06% cat final1.c
#include <stdio.h>

int strlen1(char *);  /* strdup1 and strlen1 to be */
void main(void)
{
   char s[] = "Rats&roaches";
   printf("%i\n", strlen1(s));
}

/****** NEW RECURSIVE SOLUTION */
int strlen1(char *s)
{
   if (*s == '\0') return 0;
   return strlen1(++s) + 1;
}
four06% cc -o final1 final1.c
four06% final1
12
------------------------------------------------------------------
PROBLEM 3:
four06% cat final2.c
#include <stdio.h>
#include <stdlib.h>

struct lnode {
        char data;
        struct lnode *next;
};

int listlength(struct lnode *list);
struct lnode *makelist(char *s);
void printlist(struct lnode *list);

void main(void)
{
        struct lnode *list;
        char t[] = "Why worry?";
        list = makelist(t);
        printlist(list);
        printf("\n");
        printf("%d\n", listlength(list));
}

/****** NEW RECURSIVE SOLUTION */
int listlength(struct lnode *list)
{
        if (list == NULL) return 0;
        return listlength(list -> next);
}

/****** NEW RECURSIVE FUNCTION */
void printlist(struct lnode *list)
{
        if (list != NULL) {
                printf("%c", list -> data);
                printlist(list = list -> next);
        }
}

/****** NEW RECURSIVE SOLUTION: INSERTS IN OPPOSITE ORDER */
struct lnode *makelist(char *s)
{
        struct lnode *list = NULL;
        if(*s) {
                list = (struct lnode *)
                          malloc(sizeof(struct lnode));
                list -> data = *s;
                list -> next = makelist(++s);
        }
        return list;
}
four06% cc -o final2 final2.c
four06% final2
Why worry?
0
------------------------------------------------------------------
PROBLEM 5:
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

struct tnode {
   char ch;
   struct tnode *left;
   struct tnode *right;
};
void          addtree(struct tnode *, char );
struct tnode *newnode(char );
void          treeprint(struct tnode *);
struct tnode *lookup (struct tnode *, char );
struct tnode *lookup2(struct tnode *, char );

void main(void)
{
   struct tnode *root;
   struct tnode *p;
   char c;
   root = NULL;
   while ((c = getchar()) != '\n') {
      if (root == NULL) root = newnode(c);
      else addtree(root, c);
   }
   treeprint(root);
   printf("\n");
   p = lookup(root, 'x');
   if (p == NULL) printf("Not found\n");
   else printf("Here it is: %c\n", p -> ch);
   p = lookup2(root, 'x');
   if (p == NULL) printf("Not found\n");
   else printf("Here it is: %c\n", p -> ch);
}

/* addtree: add a node, non-recursive */
void addtree(struct tnode *p, char c)
{
   for (;;) {
      if ((p -> ch) == c) return; /* ignore */
      else if ((p -> ch) > c) { /* go left */
         if ((p -> left) == NULL) {
            p -> left = newnode(c);
	    return;
         }
         else p = p -> left;
      }
      else if ((p -> ch) < c) { /* go right */
         if ((p -> right) == NULL) {
            p -> right = newnode(c);
	    return;
         }
         else p = p -> right;
      }
   }
}

/****** NEW RECURSIVE SOLUTION */
/* lookup: find the node of a char c (recursive version) */
struct tnode *lookup(struct tnode *p, char c)
{
   if (p == NULL) return NULL;
   if ((p -> ch) == c) return p;
   if ((p -> ch) > c) /* go left */
       p = lookup(p -> left, c);
   else /* if ((p -> ch) < c) */
       p = lookup(p -> right, c);
   return p;
}

/****** BETTER NON-RECURSIVE SOLUTION */
/* lookup: find the node of a char c (improved version) */
struct tnode *lookup2(struct tnode *p, char c)
{
   for (;;) {
      if (p == NULL) return NULL;
      if ((p -> ch) == c) return p;
      if ((p -> ch) > c)  /* go left */
         p = p -> left;
      else  /* if ((p -> ch) < c)   go right */
         p = p -> right;
   }
}

/* newnode: fix up a new node */
struct tnode *newnode(char c)
{
   struct tnode *p = (struct tnode *)
        malloc(sizeof(struct tnode));
   p -> ch = c;
   p -> left = p -> right = NULL;
   return p;
}

/* treeprint: recursive inorder print of tree p */
void treeprint(struct tnode *p)
{
   if (p != NULL) {
      treeprint(p -> left);
      printf("%c", p -> ch);
      treeprint(p -> right);
   }
}
four06% cc -o final5 final5.c
four06% final5
The quick brown fox jumps over the lazy dog.
 .Tabcdefghijklmnopqrstuvwxyz
Here it is: x
Here it is: x
four06% final5
The quick brown pig jumps up in the air.
 .Tabceghijkmnopqrstuw
Not found
Not found
---------------------------------------------------------------
PROBLEM 6: As the most common error, people forgot to _return_
the value from the recursive call to bin_search.  People also
didn't realize that you need to terminate the recursion first
thing in the code:
   if (p > r) return -1;
or
   if (p-r >= 1) return -1;
---------------------------------------------------------------
Good luck with the rest of your computer career.
--	Neal Wagner