Lecture 6 Recursion
Lecture 6 - Recursion
Review:Abstraction
Review: Abstraction
Describing Functions def square(x): """Return X X""" A function's domain is the set of all inputs it might possibly take as arguments. x is a number A function's range is the set of output values it might square returns a non- possibly return. negative real number A pure function's behavior is the relationship it creates square returns the square of x between input and output
Describing Functions A function's domain is the set of all inputs it might possibly take as arguments. A function's range is the set of output values it might possibly return. A pure function's behavior is the relationship it creates between input and output. def square(x): """Return X * X""" x is a number square returns a nonnegative real number square returns the square of x
Functional Abstraction Demo Mechanics Use (functional abstraction) How does Python execute this program square(2)always returns 4 line-by-line(e.g.Python Tutor) ● square(3)always returns 9 What happens when you evaluate a call expression,what goes on its body,etc. Without worrying about how Python evaluates the function
Functional Abstraction Mechanics How does Python execute this program line-by-line (e.g. Python Tutor) What happens when you evaluate a call expression, what goes on its body, etc. Use (functional abstraction) ● square(2) always returns 4 ● square(3) always returns 9 ● ... Without worrying about how Python evaluates the function Demo
Recursion
Recursion
Suppose you're waiting in line for a concert. You can't see the front of the line,but you want to know what your place in line is.Only the first 100 people get free t- shirts！ You can't step out of line because you'd lose your spot. What should you do?
Suppose you're waiting in line for a concert. You can't see the front of the line, but you want to know what your place in line is. Only the first 100 people get free tshirts! You can't step out of line because you'd lose your spot. What should you do?
An iterative algorithm might say: 1.Ask my friend to go to the front of the line. 2.Count each person in line one-by-one. 3.Then,tell me the answer
An iterative algorithm might say: 1. Ask my friend to go to the front of the line. 2. Count each person in line one-by-one. 3. Then, tell me the answer
A recursive algorithm might say: If you're at the front,you know you're first Otherwise,ask the person in front of you, "What number in line are you?" The person in front of you figures it out by asking the person in front of them who asks the person in front of them etc... Once they get an answer,they tell you and you add one to that answer
A recursive algorithm might say: • If you're at the front, you know you're first. • Otherwise, ask the person in front of you, "What number in line are you?" • The person in front of you figures it out by asking the person in front of them who asks the person in front of them etc… • Once they get an answer, they tell you and you add one to that answer
Recursion Recursion is useful for solving problems with a naturally repeating structure-they are defined in terms of themselves It requires you to find patterns of smaller problems,and to define the smallest problem possible
Recursion Recursion is useful for solving problems with a naturally repeating structure - they are defined in terms of themselves It requires you to find patterns of smaller problems, and to define the smallest problem possible
Recursion in Evaluation f(g(h(2),True),h(x)) g(h(2),True) h(x) A call expression is composed of smaller (call) expressions! h(2) Stop once you reach a number, boolean,name, etc
Recursion in Evaluation f(g(h(2), True), h(x)) g(h(2), True) h(2) h(x) A call expression is composed of smaller (call) expressions! Stop once you reach a number, boolean, name, etc