Changes 1/16/15 - Recursion and binary search trees

At NSF last night, Kevin and I talked about recursion.  He emailed me after my blog post about recursion in binary trees and mentioned that recursion is also evident in linked lists, since they are a chain of the same type of object linked to each other.

Unfortunately I didn't take a picture of his diagram, but this image sort of shows the same thing: each node links to another node, or null.  I'm still feeling a little shaky on his explanation, because I thought recursion was more of a strategy for an algorithm rather than inherently in a data structure.

Sam also wrote up and explained a cool C file that emulates the car, cdr, and cons LISP functions in C, so I have a better understanding of what those actually are doing now.

	#include <stdlib.h>
	#include <stdio.h>
	struct listnode {
	int head;
	struct listnode *tail;
	};
	struct listnode *cons(int data, struct listnode *list) {
	struct listnode *newlist = malloc(sizeof (struct listnode));
	newlist->head = data;
	newlist->tail = list;
	return newlist;
	}
	struct listnode *cdr(struct listnode *list) {
	return list->tail;
	}
	int car(struct listnode *list) {
	return list->head;
	}
	void printlist(struct listnode *list) {
	printf("%d ", car(list));
	if (cdr(list)) {
	printlist(cdr(list));
	}
	}
	int main() {
	struct listnode *list = NULL;
	list = cons(1, list);
	list = cons(2, list);
	list = cons(3, list);
	list = cons(6, cons(7, cons(8, list)));
	printlist(list);
	puts("");
	return EXIT_SUCCESS;
	}

view raw llist.c hosted with ❤ by GitHub

This program outputs

6 7 8 3 2 1

I also got further in the EIMACS binary search tree curriculum. They still haven't explained what makes a balanced search tree balanced, so I'm a little confused as to the significance. I'm pretty sure it's because that way you can guarantee that the sorted tree has the elements where you think they are, because otherwise it could be arbitrary (I know that's vague, I'll try to expand on that on Monday but I'm running out of time.)