COMP2521
Data Structures & Algorithms
Week 1.4
Recursion
1
In this lecture
Why?
While you don’t need recursion to solve a number of
problems, its a programming technique that can
substantially simplify your source code
What?
Recursion
2
Recursion
Recursion is a programming pattern where a function calls itself.
Typically, this happens during some kind of “looping”.
For/while loops are “iterative” solutions to looping, while
recrusion is a “recursive” solution
Iteration Recursion
#include
int factorial(int n) {
int product = 1;
for (int i = 1; i <= n; i++) {
product *= i;
}
return product;
}
int main(int argc, char* argv[]) {
printf("%d\n", factorial(8));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
#include
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n – 1);
}
int main(int argc, char* argv[]) {
printf(“%d\n”, factorial(8));
}
1
2
3
4
5
6
7
8
9
10
Base Case
Recursive Case
3 . 1
Fibonacci
Iteration Recursion
#include
int fibonacci(int n) {
if (n == 1) return 0;
if (n == 2) return 1;
int prevPrev = 0;
int prev = 1;
int current = 0;
for (int i = 2; i < n; i++) {
current = prevPrev + prev;
prevPrev = prev;
prev = current;
}
return current;
}
int main(int argc, char* argv[]) {
printf("%d\n", fibonacci(8));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include
int fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fibonacci(n – 1) + fibonacci(n – 2);
}
int main(int argc, char* argv[]) {
printf(“%d\n”, fibonacci(8));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Base Case
Recursive Case
A base case is what stops recursion going on forever…
3 . 2
Recursion
Is it faster? Or slower?
Does it user more memory? Or less?
3 . 3
Recursion
int length_iterative_1511(struct node *head) {
struct node *current = head;
int length = 0;
while (current != NULL) {
current = current->next;
length++;
}
}
int length_iterative_2521(struct node *head) {
int length = 0;
for (struct node *current = head; current != NULL; current = current->next) {
length++;
}
}
int length_recursive(struct node *head) {
if (head == NULL) {
return 0;
}
return 1 + length_recursive(head->next);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Let’s take a look at a linkedlist example.
3 . 4