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