Week 02 Lab Solution

Recursion

Sample Solutions

power
1
2
3
4
5
6
7
long long power(int a, int n) {
	if (n == 0) {
		return 1;
	} else {
		return a * power(a, n - 1);
	}
}
fastPower
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
long long fastPower(int a, int n) {
	if (n == 0) {
		return 1;
	}

	long long res = fastPower(a, n / 2);
	res *= res;
	if (n % 2 == 1) {
		res *= a;
	}
	return res;
}
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);
	}
}
listFunniness
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int listFunniness(struct node *list) {
	if (list == NULL) {
		return 0;
	} else if (list->value == 67) {
		return 1 + listFunniness(list->next);
	} else if (list->value == 6 &&
			(list->next != NULL && list->next->value == 7)) {
		return 1 + listFunniness(list->next);
	} else {
		return listFunniness(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;
		}
	}
}
listInsertOrdered
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
struct node *listInsertOrdered(struct node *list, int value) {
	if (list == NULL || value <= list->value) {
		struct node *n = newNode(value);
		n->next = list;
		return n;
	} else {
		list->next = listInsertOrdered(list->next, value);
		return list;
	}
}
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);
	}
}
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;
	}
}