CS计算机代考程序代写 data structure compiler INTRO TO COMPUTER SCIENCE II

INTRO TO COMPUTER SCIENCE II
RECURSION REVIEW
CS162

Last time…
▪Data Structures

Last time…Linked Lists
▪Each node contains data members and pointer ▪ “Reference” or “successor” pointer
▪The head points to the first node ▪The last node (the tail) points to null

Linked List Structure
▪Need a datatype for the node
▪Can use a struct or class depending on your
implementation
▪ Self-referential data type/structure
▪Need a class for managing the nodes
struct node{
int value
node *next; };
class LinkedList{ private:
node *head
public:
LinkedList(){ head=NULL;
} };

Linked Lists
▪How would we find the length of a linked list?

Linked Lists
▪How would we find the length of a linked list?
▪ Iteration
▪ Set of instructions repeatedly executed
▪ for loops/while loops
▪ Stops based on iteration limit
▪ Recursion
▪A function calls itself one or more times
▪ Functions
▪Stops based on a base case

Recursion
▪When a function calls itself one or more times
▪Form of repetition
▪Typically used to perform the same operation on a smaller subset and then build the result based on what is returned from the smaller case
▪Normally has at least one base case for stopping
▪Based on inductive logic
▪ Specific instances lead to general conclusion
“Win by Induction”
https://xkcd.com/1516/

Iteration vs. Recursion
▪Anything that can be done iteratively can be done recursively and vice versa
▪ Some problems naturally lend themselves towards one mode of thinking vs. the other
▪Recursion is more costly in terms of processor time and memory space
▪ Uses stack to store the set of new local variables and parameters every time the function is called
▪ Infinite recursion can lead to a system crash, vs infinite iteration just consumes CPU cycles
▪Recursion makes code smaller/more readable

Classic Example – Factorials
▪The product of an integer and all the integers below it ▪ n! = n * (n-1) * (n-2) *…* 2 * 1 for all n > 0
▪ 5! = 5 * 4 * 3 * 2 * 1 = 120
▪The base case is where n=1 ▪1! = 1 * 1 = 1

Factorial Example
▪ Iterative
int factorial(int n){ int answer;
if(n==1){
answer=1;
}else{
for(int answer=n; n>1; n–) //iteration {
answer = answer*(n-1); }
}
return answer;
}

Factorial Example
▪ Recursive
int factorial(int n){ if (n==1)
return 1;
return n*factorial(n-1); //recursive calling
}
factorial(5) factorial(4)
factorial(3)
factorial(2)
factorial(1)
return 1
return 2*1 = 2 return 3*2 = 6
return 4*6 = 24
return 5*24 = 120

Another Example – Fibonacci Series
▪1, 1, 2, 3, 5, 8, 13, 21, 34, 55…
▪F(0) = 1, F(1) = 1, F(n) = F(n-1)+F(n-2)
▪Would you use iteration or recursion to calculate out a Fibonacci number?

Another Example – Fibonacci Series
▪ Recursion
long long fibonacci(int n){ if (n>1)
return fibonacci(n-1)+fibonacci(n-2);
else
▪ Iteration
long long fibonacci(int n){ int sum = 1;
int temp1 = 1;
int temp2 = 1;
for (int i=2; i<=n; i++){ temp1 = temp2; temp2 = sum; sum = temp1 + temp2; } return sum; } } return 1; Another Example – Fibonacci Series ▪Recursive version of the previous iteration version long long fibonacci(int n, long long prev1, long long prev2) { if (n<2) return 1; else if (n==2) return prev1 + prev2; else } return fibonacci(n-1, prev2, prev1+prev2); Another Classic Example ▪Towers of Hanoi ▪ Rules ▪ Only one disk can be moved among the towers at any given time. ▪ Only the "top" disk can be removed. ▪ No large disk can sit over a small disk. solve_tower(int n, int source, int dest, int other){ if (n<=1) cout << “Move from “ << source << “ to “ << dest << “.”; else { solve_tower(n-1, source, other, dest); solve_tower(1, source, dest, other); solve_tower(n-1, other, dest, source); } Recursion ▪Common applications ▪ Language translators ▪ Compilers ▪ Sorting & searching ▪Especially with non-linear data structures ▪When should I use it? ▪ When you have a problem that can be solved by breaking it up into smaller repetitive problems that could have too many special cases for a clean iterative approach ▪And when you are OK with using more memory