南京大学：《计算机程序的构造和解释 Structure and Interpretation of Computer Programs》课程教学资源（PPT课件讲稿）06-Recursion

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 non￾negative 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 t￾shirts! 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