程序代写代做 chain algorithm Java data structure Multiple Recursion

Multiple Recursion
Daniel Archambault
CS-115: Multiple Recursion
1

Previously in CS-115
To understand recursion you need to understand recursion.
CS-115: Multiple Recursion
2

Previously in CS-115
What is recursion?
CS-115: Multiple Recursion
3

Previously in CS-115
What is recursion?
What are the two main parts to a recursive algorithm?
CS-115: Multiple Recursion
3

Previously in CS-115
What is recursion?
What are the two main parts to a recursive algorithm? What are the four stages to a recursive algorithm?
CS-115: Multiple Recursion
3

Previously in CS-115
What is recursion?
What are the two main parts to a recursive algorithm?
What are the four stages to a recursive algorithm?
What data structure is useful for tracing recursive algorithms?
CS-115: Multiple Recursion
3

Previously in CS-115
What about two recursive calls?
Multiple Recursion
CS-115: Multiple Recursion
4

Multiple Recursive Calls
What if there are multiple recursive calls?
Things get more complicated (tracing with a stack is a mess) However much of it is the same.
You have already seen this with sorting maybe…
CS-115: Multiple Recursion
5

Writing Recursive Functions
Hints to Writing Recursive Functions
Think of cases that are solved easily
􏰀 These are most likely your base cases
Figure out how to divide the data
􏰀 Division should approach simple cases
Figure out how to synthesise solution from solutions
CS-115: Multiple Recursion
6

Writing Recursive Functions
Elements of a Recursive Program:
Base Case
􏰀 Simple case of problem where we know the solution already
Break down large instance
􏰀 Input is broken down into smaller instances of the problem that
move towards the base case Recursive Case
􏰀 Apply the method being defined to the smaller instances Synthesise solution
􏰀 Larger solution is synthesised from smaller solution
CS-115: Multiple Recursion
7

Writing Recursive Functions
Steps to trace recursive programs
Start at the top and trace down
Whenever we encounter a recursive case:
􏰀 Push new stack frame
􏰀 Call the function again on its new arguments
Draw a new node on your recursion tree with line number After base case achieved:
􏰀 Return back up the recursion tree
􏰀 Start from place where function already called
CS-115: Multiple Recursion
8

Writing Recursive Functions
Tracing with recursion trees
call
return
in method

(a) (b) (c)
Number of recursive calls
public void main recFunction (…) {
… base case somewhere …
(a) recFunction (…);
(b) recFunction (…);
(c) recFunction (…);

(n) recFunction (…);
(n)
}
CS-115: Multiple Recursion
9

Writing Recursive Functions
Common Errors Writing Recursive Functions
No Base Case
􏰀
Don’t Divide Input into Parts
􏰀
CS-115: Multiple Recursion
10

Writing Recursive Functions
Common Errors Writing Recursive Functions
No Base Case
􏰀 Recurse indefinitely
Don’t Divide Input into Parts
􏰀
CS-115: Multiple Recursion
10

Writing Recursive Functions
Common Errors Writing Recursive Functions
No Base Case
􏰀 Recurse indefinitely
Don’t Divide Input into Parts
􏰀 No progress made in recursive calls
CS-115: Multiple Recursion
10

Writing Recursive Functions
Common Errors Writing Recursive Functions
No Base Case
􏰀 Recurse indefinitely
Don’t Divide Input into Parts
􏰀 No progress made in recursive calls
Don’t forget to make your recursive call
CS-115: Multiple Recursion
10

Writing Recursive Functions
Examples of Multirecursion
We’ve already seen this concept
􏰀 but, I didn’t tell you it was multirecursion
Tree traversals are naturally recursive
􏰀 visit is a call to a Java method that does work
􏰀 the other two calls are recursive calls to the traversal
CS-115: Multiple Recursion
11

Writing Recursive Functions
Preorder Traversal
Visit node and then its children
1
7
2x
4
465
1 26 357
3
public void preOrder (TreeNode n) {
visit (n);
if (n.left != null)
this.preOrder (n.left); if (n.right != null)
this.preOrder (n.right); }
CS-115: Multiple Recursion
12

Writing Recursive Functions
Inorder Traversal
If a binary search tree, this traversal would be in order
1
7
5
6
2
3 4×247
1 3651234567
public void inOrder (TreeNode n) {
if (n.left != null) this.inOrder (n.left);
visit (n);
if (n.right != null)
this.inOrder (n.right); }
CS-115: Multiple Recursion
13

Writing Recursive Functions
Postorder Traversal
Visit both children and then the node
7 146
7
6x 2 3 5
2
35
public void postOrder (TreeNode n) {
if (n.left != null) this.postOrder (n.left);
if (n.right != null) this.postOrder (n.right);
visit (n); }
1
4
CS-115: Multiple Recursion
14

Writing Recursive Functions
Find in a Binary Search Tree
Finding an element in a binary search tree is also multirecursive However, recursion tree is a chain (because of the if statement) Returns null if does not exist and the tree node if it does
public TreeNode find (String value) {
if (this.value.equals (value)) {
return this;
}
else if (this.value <= value) { if (this.left == null) { return null; } else { this.left.find (value); } } else { //same for the right if this.value > value
CS-115: Multiple Recursion
15

Writing Recursive Functions
Tracing Multirecusion
To trace multirecursion, use a (conceptual) tree
public class UhOhRecursion {
public static int numFun (int x) {
if (x == 0) {
return 1;
}
else if (x == 1) {
return 3; }
else {
return numFun (x – 2) + 2*numFun (x – 1);
} }

System.out.println (UhOhRecursion.numFun (4));
}
CS-115: Multiple Recursion
16