CS计算机代考程序代写 data structure algorithm COMP2521

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