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