Peer Instruction Materials in C++: Recursion and Factorial
Dive into the world of peer instruction materials for C++ by Cynthia Bailey Lee, exploring topics like recursion, factorial, and computer memory. Understand the concepts through interactive visuals and exercises. Discover the excitement of recursion and unravel the factorial mysteries through code examples and memory visualization. Engage with the content to enhance your C++ programming skills.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Creative Commons License CS2 in C++ Peer Instruction Materials by Cynthia Bailey Lee is licensed under a Creative Commons Attribution-NonCommercial- ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at http://peerinstruction4cs.org. CS 106X Programming Abstractions in C++ Cynthia Bailey Lee
2 CS106X: Today s Topics Recursion!!! 1. Factorial 2. Computer memory 3. Binary search
Recursion! The exclamation point isn t there only because this is so exciting, it also relates to one of our recursion examples .
Factorial! Recursive definition n! = if n is 1, then n! = 1 if n > 1, then n! = n * (n 1)! Recursive code long factorial ( int n ) { cout << n << endl; long result; if (n==1) result = 1; else result = n*factorial(n 1); return result; } What is the third thing printed when we call factorial(10)? A. 2 B. 3 C. 7 D. 8 E. Other/none/more
Factorial! Recursive definition n! = if n is 1, then n! = 1 if n > 1, then n! = n * (n 1)! Recursive code long factorial ( int n ) { cout << n << endl; long result; if (n==1) result = 1; else result = n*factorial(n 1); return result; } What is the second value ever returned when we call factorial(10)? A. 1 B. 2 C. 10 D. 90 E. Other/none/more than one
Factorial! Recursive definition n! = if n is 1, then n! = 1 if n > 1, then n! = n * (n 1)! Recursive code long factorial ( int n ) { cout << n << endl; long result; if (n==1) result = 1; else result = n*factorial(n 1); return result; } What is the fourth value ever returned when we call factorial(10)? A. 4 B. 8 C. 24 D. 90 E. Other/none/more than one
How does this look in memory? Memory Stack Heap 0
How does this look in memory? Recursive code long factorial ( int n ) { cout << n << endl; long result; if (n==1) result = 1; else result = n*factorial(n 1); return result; } Memory main() 10 0 mymethod() x: xfac: factorial() n:10 void myfunction(){ int x = 10; long xfac = 0; xfac = factorial(x); } Heap 0
How does this look in memory? Memory Memory Memory main() main() main() 10 0 10 0 10 0 mymethod() x: mymethod() x: mymethod() x: xfac: xfac: xfac: factorial() n:10 factorial() n:9 9 10 factorial() n: factorial() n:9 Heap Heap Heap
The stack part of memory is a stack Function call = push Return = pop
The stack part of memory is a stack Recursive code long factorial ( int n ) { cout << n << endl; long result; if (n==1) result = 1; else result = n*factorial(n 1); return result; } main() 4 mymethod() x: xfac: 0 factorial() n:4 void myfunction(){ int x = 4; long xfac = 0; xfac = factorial(x); } Heap
The stack part of memory is a stack Recursive code long factorial ( int n ) { cout << n << endl; long result; if (n==1) result = 1; else result = n*factorial(n 1); return result; } main() 4 mymethod() x: xfac: 0 factorial() n:4 factorial() n:3 void myfunction(){ int x = 4; long xfac = 0; xfac = factorial(x); } Heap
The stack part of memory is a stack Recursive code long factorial ( int n ) { cout << n << endl; long result; if (n==1) result = 1; else result = n*factorial(n 1); return result; } main() 4 mymethod() x: xfac: 0 factorial() n:4 factorial() n:3 factorial() n:2 void myfunction(){ int x = 4; long xfac = 0; xfac = factorial(x); } Heap
The stack part of memory is a stack Recursive code long factorial ( int n ) { cout << n << endl; long result; if (n==1) result = 1; else result = n*factorial(n 1); return result; } main() 4 mymethod() x: xfac: 0 factorial() n:4 factorial() n:3 factorial() n:2 factorial() n:1 void myfunction(){ int x = 4; long xfac = 0; xfac = factorial(x); } Heap
The stack part of memory is a stack Recursive code long factorial ( int n ) { cout << n << endl; long result; if (n==1) result = 1; else result = n*factorial(n 1); return result; } main() 4 mymethod() x: xfac: 0 factorial() n:4 factorial() n:3 factorial() n:2 factorial() n:1 void myfunction(){ int x = 4; long xfac = 0; xfac = factorial(x); } Return 1 Heap
The stack part of memory is a stack Recursive code long factorial ( int n ) { cout << n << endl; long result; if (n==1) result = 1; else result = n*factorial(n 1); return result; } main() 4 mymethod() x: xfac: 0 factorial() n:4 factorial() n:3 factorial() n:2 Return 2 void myfunction(){ int x = 4; long xfac = 0; xfac = factorial(x); } Heap
The stack part of memory is a stack Recursive code long factorial ( int n ) { cout << n << endl; long result; if (n==1) result = 1; else result = n*factorial(n 1); return result; } main() 4 mymethod() x: xfac: 0 factorial() n:4 factorial() n:3 Return 6 void myfunction(){ int x = 4; long xfac = 0; xfac = factorial(x); } Heap
The stack part of memory is a stack Recursive code long factorial ( int n ) { cout << n << endl; long result; if (n==1) result = 1; else result = n*factorial(n 1); return result; } main() 4 mymethod() x: xfac: 0 factorial() n:4 Return 24 void myfunction(){ int x = 4; long xfac = 0; xfac = factorial(x); } Heap
The stack part of memory is a stack Recursive code long factorial ( int n ) { cout << n << endl; long result; if (n==1) result = 1; else result = n*factorial(n 1); return result; } main() 4 24 mymethod() x: xfac: void myfunction(){ int x = 4; long xfac = 0; xfac = factorial(x); } Heap
Factorial! Iterative version Recursive version long factorial(int n) { long f = 1; while ( n > 1 ) { f = f * n; n = n 1; } return f; } long factorial ( int n ) { cout << n << endl; long result; if (n==1) result = 1; else result = n*factorial(n 1); return result; } NOTE: sometimes iterative can be much faster because it doesn t have to push and pop stack frames. Method calls have overhead in terms of space and time to set up and tear down.
Classic CS problem: searching
Imagine storing sorted data in an array How long does it take us to find a number we are looking for? 0 2 1 7 2 8 3 13 4 25 5 29 6 33 7 51 8 89 9 90 10 95
Imagine storing sorted data in an array How long does it take us to find a number we are looking for? 0 2 1 7 2 8 3 13 4 25 5 29 6 33 7 51 8 89 9 90 10 95 If you start at the front and proceed forward, each item you examine rules out 1 item
Imagine storing sorted data in an array 0 2 1 7 2 8 3 13 4 25 5 29 6 33 7 51 8 89 9 90 10 95 If instead we jump right to the middle, one of three things can happen: The middle one happens to be the number we were looking for, yay! We realize we went too far We realize we didn t go far enough 1. 2. 3.
Imagine storing sorted data in an array 0 2 1 7 2 8 3 13 4 25 5 29 6 33 7 51 8 89 9 90 10 95 If instead we jump right to the middle, one of three things can happen: The middle one happens to be the number we were looking for, yay! We realize we went too far We realize we didn t go far enough Ruling out HALF the options in one step is so much faster than only ruling out one! 1. 2. 3.
Binary search 0 2 1 7 2 8 3 13 4 25 5 29 6 33 7 51 8 89 9 90 10 95 Let s say the answer was 3, we didn t go far enough We ruled out the entire first half, and now only have the second half to search We could start at the front of the second half and proceed forward
Binary search 0 2 1 7 2 8 3 13 4 25 5 29 6 33 7 51 8 89 9 90 10 95 Let s say the answer was 3, we didn t go far enough We ruled out the entire first half, and now only have the second half to search We could start at the front of the second half and proceed forward but why do that when we know we have a better way? Jump right to the middle of the region to search
Binary search 0 2 1 7 2 8 3 13 4 25 5 29 6 33 7 51 8 89 9 90 10 95 Let s say the answer was 3, we didn t go far enough We ruled out the entire first half, and now only have the second half to search We could start at the front of the second half and proceed forward but why do that when we know we have a better way? Jump right to the middle of the region to search RECURSION !!
To write a recursive function, we need base case(s) and recursive call(s) What would be a good base case for our Binary Search function? A. Only three items remain: save yourself an unnecessary function call that would trivially divide them into halves of size 1, and just check all three. B. Only two items remain: can t divide into two halves with a middle, so just check the two. C. Only one item remains: just check it. D. No items remain: obviously we didn t find it. E. More than one
[Remainder of slides are for Monday 1/20]
Binary Search bool binarySearch(Vector<int> data, int key){ return binarySearch(data, key, 0, data.size()-1); } bool binarySearch(Vector<int> data, int key, int start, int end){ // Write code to handle the base case No items remain: // obviously we didn t find it by returning false (A)if (data.size() <= 0) return false; (B)if (end-start <= 0) return false; (C)Other/none/more //to be continued }
Binary Search bool binarySearch(Vector<int> data, int key){ return binarySearch(data, key, 0, data.size()-1); } bool binarySearch(Vector<int> data, int key, int start, int end){ if (end-start <= 0) return false; int middle = start + (end-start)/2; if (data[middle] == key) return true; else if (data[middle] > key) { (A) return binarySearch(data,key,middle+1,end); (B) return binarySearch(data,key,middle,end-1); (C) return binarySearch(data,key,start,middle-1); (D) Other/none/more } // to be continued }
Binary Search bool binarySearch(Vector<int> data, int key){ return binarySearch(data, key, 0, data.size()-1); } bool binarySearch(Vector<int> data, int key, int start, int end){ if (end-start <= 0) return false; int middle = start + (end-start)/2; if (data[middle] == key) return true; else if (data[middle] > key) { return binarySearch(data,key,start,middle-1); } else { return binarySearch(data,key,middle+1,end); } }
