Week 02 Lab Solution

Recursion

Sample Solutions

gcd
1
2
3
4
5
6
7
int gcd(int a, int b) {
	if (b == 0) {
		return a;
	} else {
		return gcd(b, a % b);
	}
}
rabbits
1
2
3
4
5
6
7
8
9
long long rabbits(int months) {
	if (months == 0) {
		return 2;
	} else if (months == 1) {
		return 2;
	} else {
		return rabbits(months - 1) + rabbits(months - 2);
	}
}
listTail
1
2
3
4
5
6
7
8
9
int listTail(struct node *list) {
	assert(list != NULL);

	if (list->next == NULL) {
		return list->value;
	} else {
		return listTail(list->next);
	}
}
listMax
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int listMax(struct node *list) {
	assert(list != NULL);

	if (list->next == NULL) {
		return list->value;
	} else {
		int max = listMax(list->next);
		if (list->value > max) {
			return list->value;
		} else {
			return max;
		}
	}
}
listShift
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
struct node *listShift(struct node *list) {
	if (list == NULL || list->next == NULL) {
		return list;
	}

	struct node *newHead = listShift(list->next);
	list->next = newHead->next;
	newHead->next = list;
	return newHead;
}
listSum
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int doListSum(struct node *list);

int listSum(struct list *list) {
	return doListSum(list->head);
}

int doListSum(struct node *list) {
	if (list == NULL) {
		return 0;
	} else {
		return list->value + doListSum(list->next);
	}
}
listInsertOrdered
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
struct node *doListInsertOrdered(struct node *list, int value);

void listInsertOrdered(struct list *list, int value) {
	list->head = doListInsertOrdered(list->head, value);
}

struct node *doListInsertOrdered(struct node *head, int value) {
	if (head == NULL || value <= head->value) {
		struct node *n = newNode(value);
		n->next = head;
		return n;
	} else {
		head->next = doListInsertOrdered(head->next, value);
		return head;
	}
}
listInsertNth
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
struct node *doListInsertNth(struct node *head, int n, int value);

void listInsertNth(struct list *list, int n, int value) {
	list->head = doListInsertNth(list->head, n, value);
}

struct node *doListInsertNth(struct node *head, int n, int value) {
	if (head == NULL || n <= 0) {
		struct node *n = newNode(value);
		n->next = head;
		return n;
	} else {
		head->next = doListInsertNth(head->next, n - 1, value);
		return head;
	}
}