CAS CS 111 Lecture 9: CAS CS 111 B1 September 25 Lecture 9 Notes
25 Sep 2018
School
Department
Course
Professor
CAS CS 111 verified notes
9/38View all
Recall: Designing a Recursive Function
Start by programming the base case(s)/
What instance(s) of this problem can I solve directly
(without looking at anything smaller)?
i.
1.
Find the recursive substructure.
How could I use the solution to any smaller version of the
problem to solve the overall problem?
i.
2.
Solve the smaller problem using a recursive call!
Store its result in a variable
i.
3.
Do your one step.
Build your solution on the result of the recursive call
i.
Use concrete cases to figure out what you need to do
ii.
4.
•
Recursively Finding the Largest Element in a List
○
•
Design Questions for mymax()
(base case) - When can I determine the largest element in a list
without needing to look at a smaller list?
○
(recursive case) - How could I use the largest element in a smaller
list to determine the largest element in the entire list?
○
○
Compare the first element to largest element in the rest of the list1.
Return the larger of the two2.
LET THE RECURSIVE CALL HANDLE THE REST OF
THE LIST!
•
Recursively Finding the Largest Element in a List
○
•
How many times will max_rest be returned?
Question:
§
○
○Answer:
§
§
§
§
§
§
§
§
§
§
§
§
§
§
§
○Final Answer:
§
•
•Recursively Replacing Characters in a String
○
•Design Questions for replace()
○(base case) - When can I determine the "replaced" version of s
without looking at a smaller string?
○(recursive case) - How could I use the "replaced" version of a
smaller string to get the "replaced" version of s?
○
○
○
•Complete This Function Together!
○
○
○
○
○
○
○FINAL'VERSION!!!!!
§
•Add'Temporary'prints'for'Debugging/Tracing
○
Monday's)Lecture
Tuesday,' 25'September' 2018
6:10'PM
Recall: Designing a Recursive Function
Start by programming the base case(s)/
What instance(s) of this problem can I solve directly
(without looking at anything smaller)?
i.
1.
Find the recursive substructure.
How could I use the solution to any smaller version of the
problem to solve the overall problem?
i.
2.
Solve the smaller problem using a recursive call!
Store its result in a variablei.
3.
Do your one step.
Build your solution on the result of the recursive calli.
Use concrete cases to figure out what you need to doii.
4.
•
Recursively Finding the Largest Element in a List
○
•
Design Questions for mymax()
(base case) - When can I determine the largest element in a list
without needing to look at a smaller list?
○
(recursive case) - How could I use the largest element in a smaller
list to determine the largest element in the entire list?
○
○
Compare the first element to largest element in the rest of the list
1.
Return the larger of the two
2.
LET THE RECURSIVE CALL HANDLE THE REST OF
THE LIST!
•
Recursively Finding the Largest Element in a List
○
•
How many times will max_rest be returned?
Question:
§
○
○Answer:
§
§
§
§
§
§
§
§
§
§
§
§
§
§
§
○Final Answer:
§
•
•Recursively Replacing Characters in a String
○
•Design Questions for replace()
○(base case) - When can I determine the "replaced" version of s
without looking at a smaller string?
○(recursive case) - How could I use the "replaced" version of a
smaller string to get the "replaced" version of s?
○
○
○
•Complete This Function Together!
○
○
○
○
○
○
○FINAL'VERSION!!!!!
§
•Add'Temporary'prints'for'Debugging/Tracing
○
Monday's)Lecture
Tuesday,' 25'September' 2018 6:10'PM
Recall: Designing a Recursive Function
Start by programming the base case(s)/
What instance(s) of this problem can I solve directly
(without looking at anything smaller)?
i.
1.
Find the recursive substructure.
How could I use the solution to any smaller version of the
problem to solve the overall problem?
i.
2.
Solve the smaller problem using a recursive call!
Store its result in a variablei.
3.
Do your one step.
Build your solution on the result of the recursive calli.
Use concrete cases to figure out what you need to doii.
4.
•
Recursively Finding the Largest Element in a List
○
•
Design Questions for mymax()
(base case) - When can I determine the largest element in a list
without needing to look at a smaller list?
○
(recursive case) - How could I use the largest element in a smaller
list to determine the largest element in the entire list?
○
○
Compare the first element to largest element in the rest of the list1.
Return the larger of the two2.
LET THE RECURSIVE CALL HANDLE THE REST OF
THE LIST!
•
Recursively Finding the Largest Element in a List
○
•
How many times will max_rest be returned?
Question:
§
○
○
Answer:
§
§
§
§
§
§
§
§
§
§
§
§
§
§
§
○Final Answer:
§
•
•Recursively Replacing Characters in a String
○
•Design Questions for replace()
○(base case) - When can I determine the "replaced" version of s
without looking at a smaller string?
○(recursive case) - How could I use the "replaced" version of a
smaller string to get the "replaced" version of s?
○
○
○
•Complete This Function Together!
○
○
○
○
○
○
○FINAL'VERSION!!!!!
§
•Add'Temporary'prints'for'Debugging/Tracing
○
Monday's)Lecture
Tuesday,' 25'September' 2018 6:10'PM
![I&C SCI 33 Lecture 13: [Recursive Functions] thumbnail](https://new-docs-thumbs.oneclass.com/doc_thumbnails/new_mobile/1528134-class-notes-us-uc-irvine-i-c-sci-33-lecture13.jpg)