|
|
| Line 1: |
Line 1: |
| <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
| | {{Think Python/Page}} |
| "http://www.w3.org/TR/REC-html40/loose.dtd">
| |
| <HTML>
| |
| <HEAD>
| |
|
| |
|
| <META http-equiv="Content-Type" content="text/html; charset=US-ASCII">
| | == Chapter 6  Fruitful functions == |
| <META name="GENERATOR" content="hevea 1.10">
| | |
| <LINK rel="stylesheet" type="text/css" href="book.css">
| | |
| <TITLE>Fruitful functions</TITLE>
| | |
| </HEAD>
| | === 6.1  Return values === |
| <BODY >
| | |
| <A HREF="book006.html"><IMG SRC="previous_motif.gif" ALT="Previous"></A>
| | |
| <A HREF="index.html"><IMG SRC="contents_motif.gif" ALT="Up"></A>
| | |
| <A HREF="book008.html"><IMG SRC="next_motif.gif" ALT="Next"></A>
| | |
| <HR>
| | Some of the built-in functions we have used, such as the math |
| <H1 CLASS="chapter"><A NAME="htoc72"><FONT COLOR=black><FONT SIZE=3>Chapter 6</FONT></FONT></A><FONT COLOR=black><FONT SIZE=3>  Fruitful functions</FONT></FONT></H1><P><FONT COLOR=black><FONT SIZE=3>
| |
| </FONT></FONT><A NAME="fruitchap"></A></P><H2 CLASS="section"><A NAME="toc65"></A><A NAME="htoc73"><FONT COLOR=black><FONT SIZE=3>6.1</FONT></FONT></A><FONT COLOR=black><FONT SIZE=3>  Return values</FONT></FONT></H2><P><FONT COLOR=black><FONT SIZE=3>
| |
| </FONT></FONT><A NAME="@default440"></A></P><P><FONT COLOR=black><FONT SIZE=3>Some of the built-in functions we have used, such as the math
| |
| functions, produce results. Calling the function generates a | | functions, produce results. Calling the function generates a |
| value, which we usually assign to a variable or use as part of an | | value, which we usually assign to a variable or use as part of an |
| expression.</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>e = math.exp(1.0) | | expression. |
| | <PRE CLASS="verbatim">e = math.exp(1.0) |
| height = radius * math.sin(radians) | | height = radius * math.sin(radians) |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>All of the functions we have written so far are void; they print
| | </PRE> |
| something or move turtles around, but their return value is </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>None</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>.</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>In this chapter, we are (finally) going to write fruitful functions. | | All of the functions we have written so far are void; they print |
| The first example is </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>area</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>, which returns the area of a circle | | something or move turtles around, but their return value is <TT>None</TT>. |
| with the given radius:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def area(radius): | | |
| | In this chapter, we are (finally) going to write fruitful functions. |
| | The first example is <TT>area</TT>, which returns the area of a circle |
| | with the given radius: |
| | <PRE CLASS="verbatim">def area(radius): |
| temp = math.pi * radius**2 | | temp = math.pi * radius**2 |
| return temp | | return temp |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>We have seen the </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>return</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> statement before, but in a fruitful
| | </PRE> |
| function the </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>return</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> statement includes | | We have seen the <TT>return</TT> statement before, but in a fruitful |
| | function the <TT>return</TT> statement includes |
| an expression. This statement means: “Return immediately from | | an expression. This statement means: “Return immediately from |
| this function and use the following expression as a return value.” | | this function and use the following expression as a return value.” |
| The expression can be arbitrarily complicated, so we could | | The expression can be arbitrarily complicated, so we could |
| have written this function more concisely:</FONT></FONT></P><P><A NAME="@default441"></A><FONT COLOR=black><FONT SIZE=3> | | have written this function more concisely: |
| </FONT></FONT><A NAME="@default442"></A></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def area(radius):
| | |
| | |
| | |
| | <PRE CLASS="verbatim">def area(radius): |
| return math.pi * radius**2 | | return math.pi * radius**2 |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>On the other hand, </FONT></FONT><FONT COLOR=black><FONT SIZE=3><B>temporary variables</B></FONT></FONT><FONT COLOR=black><FONT SIZE=3> like </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>temp</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> often make
| | </PRE> |
| debugging easier.</FONT></FONT></P><P><A NAME="@default443"></A><FONT COLOR=black><FONT SIZE=3> | | On the other hand, '''temporary variables''' like <TT>temp</TT> often make |
| </FONT></FONT><A NAME="@default444"></A></P><P><FONT COLOR=black><FONT SIZE=3>Sometimes it is useful to have multiple return statements, one in each
| | debugging easier. |
| branch of a conditional:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def absolute_value(x): | | |
| | |
| | |
| | |
| | Sometimes it is useful to have multiple return statements, one in each |
| | branch of a conditional: |
| | <PRE CLASS="verbatim">def absolute_value(x): |
| if x < 0: | | if x < 0: |
| return -x | | return -x |
| else: | | else: |
| return x | | return x |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>Since these </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>return</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> statements are in an alternative conditional,
| | </PRE> |
| only one will be executed.</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>As soon as a return statement executes, the function | | Since these <TT>return</TT> statements are in an alternative conditional, |
| | only one will be executed. |
| | |
| | As soon as a return statement executes, the function |
| terminates without executing any subsequent statements. | | terminates without executing any subsequent statements. |
| Code that appears after a </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>return</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> statement, or any other place | | Code that appears after a <TT>return</TT> statement, or any other place |
| the flow of execution can never reach, is called </FONT></FONT><FONT COLOR=black><FONT SIZE=3><B>dead code</B></FONT></FONT><FONT COLOR=black><FONT SIZE=3>.</FONT></FONT></P><P><A NAME="@default445"></A></P><P><FONT COLOR=black><FONT SIZE=3>In a fruitful function, it is a good idea to ensure | | the flow of execution can never reach, is called '''dead code'''. |
| | |
| | In a fruitful function, it is a good idea to ensure |
| that every possible path through the program hits a | | that every possible path through the program hits a |
| </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>return</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> statement. For example:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def absolute_value(x):
| | <TT>return</TT> statement. For example: |
| | <PRE CLASS="verbatim">def absolute_value(x): |
| if x < 0: | | if x < 0: |
| return -x | | return -x |
| if x > 0: | | if x > 0: |
| return x | | return x |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>This function is incorrect because if </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>x</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> happens to be 0,
| | </PRE> |
| | This function is incorrect because if <TT>x</TT> happens to be 0, |
| neither condition is true, and the function ends without hitting a | | neither condition is true, and the function ends without hitting a |
| </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>return</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> statement. If the flow of execution gets to the end
| | <TT>return</TT> statement. If the flow of execution gets to the end |
| of a function, the return value is </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>None</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>, which is not | | of a function, the return value is <TT>None</TT>, which is not |
| the absolute value of 0.</FONT></FONT></P><P><A NAME="@default446"></A><FONT COLOR=black><FONT SIZE=3> | | the absolute value of 0. |
| </FONT></FONT><A NAME="@default447"></A></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>>>> print absolute_value(0)
| | |
| | |
| | |
| | <PRE CLASS="verbatim">>>> print absolute_value(0) |
| None | | None |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>By the way, Python provides a built-in function called
| | </PRE> |
| </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>abs</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> that computes absolute values.</FONT></FONT></P><P><A NAME="@default448"></A><FONT COLOR=black><FONT SIZE=3>
| | By the way, Python provides a built-in function called |
| </FONT></FONT><A NAME="@default449"></A></P><DIV CLASS="theorem"><FONT COLOR=black><FONT SIZE=3><B>Exercise 1</B></FONT></FONT><FONT COLOR=black><FONT SIZE=3>  </FONT></FONT><P><A NAME="@default450"></A><FONT COLOR=black><FONT SIZE=3><EM>
| | <TT>abs</TT> that computes absolute values. |
| </EM></FONT></FONT><A NAME="@default451"></A></P><P><FONT COLOR=black><FONT SIZE=3><EM>Write a </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>compare</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> function
| | |
| that returns </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>1</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> if </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>x > y</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>, | | |
| </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>0</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> if </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>x == y</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>, and </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>-1</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> if </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>x < y</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>.
| | |
| </EM></FONT></FONT></P></DIV><H2 CLASS="section"><A NAME="toc66"></A><A NAME="htoc74"><FONT COLOR=black><FONT SIZE=3>6.2</FONT></FONT></A><FONT COLOR=black><FONT SIZE=3>  Incremental development</FONT></FONT></H2><P><FONT COLOR=black><FONT SIZE=3>
| | <DIV CLASS="theorem">'''Exercise 1'''   |
| </FONT></FONT><A NAME="incremental development"></A><FONT COLOR=black><FONT SIZE=3>
| | '' |
| </FONT></FONT><A NAME="@default452"></A></P><P><FONT COLOR=black><FONT SIZE=3>As you write larger functions, you might find yourself
| | '' |
| spending more time debugging.</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>To deal with increasingly complex programs, | | |
| | ''Write a ''''<TT>compare</TT>'''' function |
| | that returns ''''<TT>1</TT>'''' if ''''<TT>x > y</TT>'''', |
| | ''''<TT>0</TT>'''' if ''''<TT>x == y</TT>'''', and ''''<TT>-1</TT>'''' if ''''<TT>x < y</TT>''''. |
| | '' |
| | </DIV>=== 6.2  Incremental development === |
| | |
| | |
| | |
| | |
| | |
| | As you write larger functions, you might find yourself |
| | spending more time debugging. |
| | |
| | To deal with increasingly complex programs, |
| you might want to try a process called | | you might want to try a process called |
| </FONT></FONT><FONT COLOR=black><FONT SIZE=3><B>incremental development</B></FONT></FONT><FONT COLOR=black><FONT SIZE=3>. The goal of incremental development
| | '''incremental development'''. The goal of incremental development |
| is to avoid long debugging sessions by adding and testing only | | is to avoid long debugging sessions by adding and testing only |
| a small amount of code at a time.</FONT></FONT></P><P><A NAME="@default453"></A><FONT COLOR=black><FONT SIZE=3> | | a small amount of code at a time. |
| </FONT></FONT><A NAME="@default454"></A></P><P><FONT COLOR=black><FONT SIZE=3>As an example, suppose you want to find the distance between two
| | |
| points, given by the coordinates </FONT></FONT><FONT COLOR=black><FONT SIZE=3>(<I>x</I></FONT></FONT><SUB><FONT COLOR=black><FONT SIZE=3>1</FONT></FONT></SUB><FONT COLOR=black><FONT SIZE=3>, <I>y</I></FONT></FONT><SUB><FONT COLOR=black><FONT SIZE=3>1</FONT></FONT></SUB><FONT COLOR=black><FONT SIZE=3>)</FONT></FONT><FONT COLOR=black><FONT SIZE=3> and </FONT></FONT><FONT COLOR=black><FONT SIZE=3>(<I>x</I></FONT></FONT><SUB><FONT COLOR=black><FONT SIZE=3>2</FONT></FONT></SUB><FONT COLOR=black><FONT SIZE=3>, <I>y</I></FONT></FONT><SUB><FONT COLOR=black><FONT SIZE=3>2</FONT></FONT></SUB><FONT COLOR=black><FONT SIZE=3>)</FONT></FONT><FONT COLOR=black><FONT SIZE=3>. | | |
| By the Pythagorean theorem, the distance is:</FONT></FONT></P><TABLE CLASS="display dcenter"><TR VALIGN="middle"><TD CLASS="dcell"><FONT COLOR=black><FONT SIZE=3><I>distance</I></FONT></FONT><FONT COLOR=black><FONT SIZE=3> = </FONT></FONT></TD><TD CLASS="dcell"><FONT COLOR=black><FONT SIZE=5>√</FONT></FONT></TD><TD CLASS="dcell"><TABLE border=0 cellspacing=1 cellpadding=0><TR><TD CLASS="hbar"><FONT COLOR=black><FONT SIZE=3></FONT></FONT></TD></TR> | | |
| <TR><TD ALIGN=center NOWRAP><FONT COLOR=black><FONT SIZE=3>(<I>x</I></FONT></FONT><SUB><FONT COLOR=black><FONT SIZE=3>2</FONT></FONT></SUB><FONT COLOR=black><FONT SIZE=3> − <I>x</I></FONT></FONT><SUB><FONT COLOR=black><FONT SIZE=3>1</FONT></FONT></SUB><FONT COLOR=black><FONT SIZE=3>)</FONT></FONT><SUP><FONT COLOR=black><FONT SIZE=3>2</FONT></FONT></SUP><FONT COLOR=black><FONT SIZE=3> + (<I>y</I></FONT></FONT><SUB><FONT COLOR=black><FONT SIZE=3>2</FONT></FONT></SUB><FONT COLOR=black><FONT SIZE=3> − <I>y</I></FONT></FONT><SUB><FONT COLOR=black><FONT SIZE=3>1</FONT></FONT></SUB><FONT COLOR=black><FONT SIZE=3>)</FONT></FONT><SUP><FONT COLOR=black><FONT SIZE=3>2</FONT></FONT></SUP></TD></TR> | | |
| | As an example, suppose you want to find the distance between two |
| | points, given by the coordinates (<I>x</I><SUB>1</SUB>, <I>y</I><SUB>1</SUB>) and (<I>x</I><SUB>2</SUB>, <I>y</I><SUB>2</SUB>). |
| | By the Pythagorean theorem, the distance is: |
| | <TABLE CLASS="display dcenter"><TR VALIGN="middle"><TD CLASS="dcell"><I>distance</I> = </TD><TD CLASS="dcell">√</TD><TD CLASS="dcell"><TABLE border=0 cellspacing=1 cellpadding=0><TR><TD CLASS="hbar"></TD></TR> |
| | <TR><TD ALIGN=center NOWRAP>(<I>x</I><SUB>2</SUB> − <I>x</I><SUB>1</SUB>)<SUP>2</SUP> + (<I>y</I><SUB>2</SUB> − <I>y</I><SUB>1</SUB>)<SUP>2</SUP></TD></TR> |
| </TABLE></TD></TR> | | </TABLE></TD></TR> |
| </TABLE><P><FONT COLOR=black><FONT SIZE=3> | | </TABLE> |
| The first step is to consider what a </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>distance</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> function should | | |
| | The first step is to consider what a <TT>distance</TT> function should |
| look like in Python. In other words, what are the inputs (parameters) | | look like in Python. In other words, what are the inputs (parameters) |
| and what is the output (return value)?</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>In this case, the inputs are two points, which you can represent | | and what is the output (return value)? |
| | |
| | In this case, the inputs are two points, which you can represent |
| using four numbers. The return value is the distance, which is | | using four numbers. The return value is the distance, which is |
| a floating-point value.</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>Already you can write an outline of the function:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def distance(x1, y1, x2, y2): | | a floating-point value. |
| | |
| | Already you can write an outline of the function: |
| | <PRE CLASS="verbatim">def distance(x1, y1, x2, y2): |
| return 0.0 | | return 0.0 |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>Obviously, this version doesn’t compute distances; it always returns
| | </PRE> |
| | Obviously, this version doesn’t compute distances; it always returns |
| zero. But it is syntactically correct, and it runs, which means that | | zero. But it is syntactically correct, and it runs, which means that |
| you can test it before you make it more complicated.</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>To test the new function, call it with sample arguments:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>>>> distance(1, 2, 4, 6) | | you can test it before you make it more complicated. |
| | |
| | To test the new function, call it with sample arguments: |
| | <PRE CLASS="verbatim">>>> distance(1, 2, 4, 6) |
| 0.0 | | 0.0 |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>I chose these values so that the horizontal distance is 3 and the
| | </PRE> |
| | I chose these values so that the horizontal distance is 3 and the |
| vertical distance is 4; that way, the result is 5 | | vertical distance is 4; that way, the result is 5 |
| (the hypotenuse of a 3-4-5 triangle). When testing a function, it is | | (the hypotenuse of a 3-4-5 triangle). When testing a function, it is |
| useful to know the right answer.</FONT></FONT></P><P><A NAME="@default455"></A></P><P><FONT COLOR=black><FONT SIZE=3>At this point we have confirmed that the function is syntactically | | useful to know the right answer. |
| | |
| | At this point we have confirmed that the function is syntactically |
| correct, and we can start adding code to the body. | | correct, and we can start adding code to the body. |
| A reasonable next step is to find the differences | | A reasonable next step is to find the differences |
| </FONT></FONT><FONT COLOR=black><FONT SIZE=3><I>x</I></FONT></FONT><SUB><FONT COLOR=black><FONT SIZE=3>2</FONT></FONT></SUB><FONT COLOR=black><FONT SIZE=3> − <I>x</I></FONT></FONT><SUB><FONT COLOR=black><FONT SIZE=3>1</FONT></FONT></SUB><FONT COLOR=black><FONT SIZE=3> and </FONT></FONT><FONT COLOR=black><FONT SIZE=3><I>y</I></FONT></FONT><SUB><FONT COLOR=black><FONT SIZE=3>2</FONT></FONT></SUB><FONT COLOR=black><FONT SIZE=3> − <I>y</I></FONT></FONT><SUB><FONT COLOR=black><FONT SIZE=3>1</FONT></FONT></SUB><FONT COLOR=black><FONT SIZE=3>. The next version stores those values in
| | <I>x</I><SUB>2</SUB> − <I>x</I><SUB>1</SUB> and <I>y</I><SUB>2</SUB> − <I>y</I><SUB>1</SUB>. The next version stores those values in |
| temporary variables and prints them.</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def distance(x1, y1, x2, y2): | | temporary variables and prints them. |
| | <PRE CLASS="verbatim">def distance(x1, y1, x2, y2): |
| dx = x2 - x1 | | dx = x2 - x1 |
| dy = y2 - y1 | | dy = y2 - y1 |
| Line 104: |
Line 156: |
| print 'dy is', dy | | print 'dy is', dy |
| return 0.0 | | return 0.0 |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>If the function is working, it should display </FONT></FONT><CODE><FONT COLOR=black><FONT SIZE=3>'dx is 3'</FONT></FONT></CODE><FONT COLOR=black><FONT SIZE=3> and </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>’dy is 4’</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>. If so, we know that the function is getting the right
| | </PRE> |
| | If the function is working, it should display <CODE>'dx is 3'</CODE> and <TT>’dy is 4’</TT>. If so, we know that the function is getting the right |
| arguments and performing the first computation correctly. If not, | | arguments and performing the first computation correctly. If not, |
| there are only a few lines to check.</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>Next we compute the sum of squares of </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>dx</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> and </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>dy</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def distance(x1, y1, x2, y2): | | there are only a few lines to check. |
| | |
| | Next we compute the sum of squares of <TT>dx</TT> and <TT>dy</TT>: |
| | <PRE CLASS="verbatim">def distance(x1, y1, x2, y2): |
| dx = x2 - x1 | | dx = x2 - x1 |
| dy = y2 - y1 | | dy = y2 - y1 |
| Line 112: |
Line 168: |
| print 'dsquared is: ', dsquared | | print 'dsquared is: ', dsquared |
| return 0.0 | | return 0.0 |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>Again, you would run the program at this stage and check the output
| | </PRE> |
| | Again, you would run the program at this stage and check the output |
| (which should be 25). | | (which should be 25). |
| Finally, you can use </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>math.sqrt</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> to compute and return the result:</FONT></FONT></P><P><A NAME="@default456"></A><FONT COLOR=black><FONT SIZE=3> | | Finally, you can use <TT>math.sqrt</TT> to compute and return the result: |
| </FONT></FONT><A NAME="@default457"></A></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def distance(x1, y1, x2, y2):
| | |
| | |
| | |
| | <PRE CLASS="verbatim">def distance(x1, y1, x2, y2): |
| dx = x2 - x1 | | dx = x2 - x1 |
| dy = y2 - y1 | | dy = y2 - y1 |
| Line 121: |
Line 181: |
| result = math.sqrt(dsquared) | | result = math.sqrt(dsquared) |
| return result | | return result |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>If that works correctly, you are done. Otherwise, you might
| | </PRE> |
| want to print the value of </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>result</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> before the return | | If that works correctly, you are done. Otherwise, you might |
| statement.</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>The final version of the function doesn’t display anything when it | | want to print the value of <TT>result</TT> before the return |
| runs; it only returns a value. The </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>print</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> statements we wrote | | statement. |
| | |
| | The final version of the function doesn’t display anything when it |
| | runs; it only returns a value. The <TT>print</TT> statements we wrote |
| are useful for debugging, but once you get the function working, you | | are useful for debugging, but once you get the function working, you |
| should remove them. Code like that is called </FONT></FONT><FONT COLOR=black><FONT SIZE=3><B>scaffolding</B></FONT></FONT><FONT COLOR=black><FONT SIZE=3> | | should remove them. Code like that is called '''scaffolding''' |
| because it is helpful for building the program but is not part of the | | because it is helpful for building the program but is not part of the |
| final product.</FONT></FONT></P><P><A NAME="@default458"></A></P><P><FONT COLOR=black><FONT SIZE=3>When you start out, you should add only a line or two of code at a | | final product. |
| | |
| | When you start out, you should add only a line or two of code at a |
| time. As you gain more experience, you might find yourself writing | | time. As you gain more experience, you might find yourself writing |
| and debugging bigger chunks. Either way, incremental development | | and debugging bigger chunks. Either way, incremental development |
| can save you a lot of debugging time.</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>The key aspects of the process are:</FONT></FONT></P><OL CLASS="enumerate" type=1><LI CLASS="li-enumerate"><FONT COLOR=black><FONT SIZE=3>Start with a working program and make small incremental changes. | | can save you a lot of debugging time. |
| | |
| | The key aspects of the process are: |
| | |
| | *Start with a working program and make small incremental changes. |
| At any point, if there is an error, you should have a good idea | | At any point, if there is an error, you should have a good idea |
| where it is.</FONT></FONT></LI><LI CLASS="li-enumerate"><FONT COLOR=black><FONT SIZE=3>Use temporary variables to hold intermediate values so you can | | where it is. |
| display and check them.</FONT></FONT></LI><LI CLASS="li-enumerate"><FONT COLOR=black><FONT SIZE=3>Once the program is working, you might want to remove some of | | |
| | *Use temporary variables to hold intermediate values so you can |
| | display and check them. |
| | |
| | *Once the program is working, you might want to remove some of |
| the scaffolding or consolidate multiple statements into compound | | the scaffolding or consolidate multiple statements into compound |
| expressions, but only if it does not make the program difficult to | | expressions, but only if it does not make the program difficult to |
| read.</FONT></FONT></LI></OL><DIV CLASS="theorem"><FONT COLOR=black><FONT SIZE=3><B>Exercise 2</B></FONT></FONT><FONT COLOR=black><FONT SIZE=3>  </FONT></FONT><P><A NAME="@default459"></A></P><P><FONT COLOR=black><FONT SIZE=3><EM>Use incremental development to write a function | | read. |
| called </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>hypotenuse</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> that returns the length of the hypotenuse of a | | |
| | <DIV CLASS="theorem">'''Exercise 2'''   |
| | |
| | ''Use incremental development to write a function |
| | called ''''<TT>hypotenuse</TT>'''' that returns the length of the hypotenuse of a |
| right triangle given the lengths of the two legs as arguments. | | right triangle given the lengths of the two legs as arguments. |
| Record each stage of the development process as you go. | | Record each stage of the development process as you go. |
| </EM></FONT></FONT></P></DIV><H2 CLASS="section"><A NAME="toc67"></A><A NAME="htoc75"><FONT COLOR=black><FONT SIZE=3>6.3</FONT></FONT></A><FONT COLOR=black><FONT SIZE=3>  Composition</FONT></FONT></H2><P><A NAME="@default460"></A><FONT COLOR=black><FONT SIZE=3>
| | '' |
| </FONT></FONT><A NAME="@default461"></A></P><P><FONT COLOR=black><FONT SIZE=3>As you should expect by now, you can call one function from
| | </DIV>=== 6.3  Composition === |
| within another. This ability is called </FONT></FONT><FONT COLOR=black><FONT SIZE=3><B>composition</B></FONT></FONT><FONT COLOR=black><FONT SIZE=3>.</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>As an example, we’ll write a function that takes two points, | | |
| | |
| | |
| | |
| | As you should expect by now, you can call one function from |
| | within another. This ability is called '''composition'''. |
| | |
| | As an example, we’ll write a function that takes two points, |
| the center of the circle and a point on the perimeter, and computes | | the center of the circle and a point on the perimeter, and computes |
| the area of the circle.</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>Assume that the center point is stored in the variables </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>xc</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> and | | the area of the circle. |
| </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>yc</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>, and the perimeter point is in </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>xp</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> and </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>yp</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>. The
| | |
| | Assume that the center point is stored in the variables <TT>xc</TT> and |
| | <TT>yc</TT>, and the perimeter point is in <TT>xp</TT> and <TT>yp</TT>. The |
| first step is to find the radius of the circle, which is the distance | | first step is to find the radius of the circle, which is the distance |
| between the two points. We just wrote a function, </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>distance</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>, that does that:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>radius = distance(xc, yc, xp, yp) | | between the two points. We just wrote a function, <TT>distance</TT>, that does that: |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>The next step is to find the area of a circle with that radius;
| | <PRE CLASS="verbatim">radius = distance(xc, yc, xp, yp) |
| we just wrote that, too:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>result = area(radius) | | </PRE> |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>Encapsulating these steps in a function, we get:</FONT></FONT></P><P><A NAME="@default462"></A></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def circle_area(xc, yc, xp, yp):
| | The next step is to find the area of a circle with that radius; |
| | we just wrote that, too: |
| | <PRE CLASS="verbatim">result = area(radius) |
| | </PRE> |
| | Encapsulating these steps in a function, we get: |
| | |
| | <PRE CLASS="verbatim">def circle_area(xc, yc, xp, yp): |
| radius = distance(xc, yc, xp, yp) | | radius = distance(xc, yc, xp, yp) |
| result = area(radius) | | result = area(radius) |
| return result | | return result |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>The temporary variables </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>radius</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> and </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>result</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> are useful for
| | </PRE> |
| | The temporary variables <TT>radius</TT> and <TT>result</TT> are useful for |
| development and debugging, but once the program is working, we can | | development and debugging, but once the program is working, we can |
| make it more concise by composing the function calls:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def circle_area(xc, yc, xp, yp): | | make it more concise by composing the function calls: |
| | <PRE CLASS="verbatim">def circle_area(xc, yc, xp, yp): |
| return area(distance(xc, yc, xp, yp)) | | return area(distance(xc, yc, xp, yp)) |
| </FONT></FONT></PRE><H2 CLASS="section"><A NAME="toc68"></A><A NAME="htoc76"><FONT COLOR=black><FONT SIZE=3>6.4</FONT></FONT></A><FONT COLOR=black><FONT SIZE=3>  Boolean functions</FONT></FONT></H2><P><FONT COLOR=black><FONT SIZE=3>
| | </PRE>=== 6.4  Boolean functions === |
| </FONT></FONT><A NAME="boolean"></A></P><P><A NAME="@default463"></A></P><P><FONT COLOR=black><FONT SIZE=3>Functions can return booleans, which is often convenient for hiding
| | |
| complicated tests inside functions. For example:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def is_divisible(x, y): | | |
| | |
| | |
| | Functions can return booleans, which is often convenient for hiding |
| | complicated tests inside functions. For example: |
| | <PRE CLASS="verbatim">def is_divisible(x, y): |
| if x % y == 0: | | if x % y == 0: |
| return True | | return True |
| else: | | else: |
| return False | | return False |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>It is common to give boolean functions names that sound like yes/no
| | </PRE> |
| questions; </FONT></FONT><CODE><FONT COLOR=black><FONT SIZE=3>is_divisible</FONT></FONT></CODE><FONT COLOR=black><FONT SIZE=3> returns either </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>True</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> or </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>False</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> | | It is common to give boolean functions names that sound like yes/no |
| to indicate whether </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>x</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> is divisible by </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>y</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>.</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>Here is an example:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>>>> is_divisible(6, 4) | | questions; <CODE>is_divisible</CODE> returns either <TT>True</TT> or <TT>False</TT> |
| | to indicate whether <TT>x</TT> is divisible by <TT>y</TT>. |
| | |
| | Here is an example: |
| | <PRE CLASS="verbatim">>>> is_divisible(6, 4) |
| False | | False |
| >>> is_divisible(6, 3) | | >>> is_divisible(6, 3) |
| True | | True |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>The result of the </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>==</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> operator is a boolean, so we can write the
| | </PRE> |
| function more concisely by returning it directly:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def is_divisible(x, y): | | The result of the <TT>==</TT> operator is a boolean, so we can write the |
| | function more concisely by returning it directly: |
| | <PRE CLASS="verbatim">def is_divisible(x, y): |
| return x % y == 0 | | return x % y == 0 |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>Boolean functions are often used in conditional statements:</FONT></FONT></P><P><A NAME="@default464"></A><FONT COLOR=black><FONT SIZE=3>
| | </PRE> |
| </FONT></FONT><A NAME="@default465"></A></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>if is_divisible(x, y):
| | Boolean functions are often used in conditional statements: |
| | |
| | |
| | |
| | <PRE CLASS="verbatim">if is_divisible(x, y): |
| print 'x is divisible by y' | | print 'x is divisible by y' |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>It might be tempting to write something like:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>if is_divisible(x, y) == True:
| | </PRE> |
| | It might be tempting to write something like: |
| | <PRE CLASS="verbatim">if is_divisible(x, y) == True: |
| print 'x is divisible by y' | | print 'x is divisible by y' |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>But the extra comparison is unnecessary.</FONT></FONT></P><DIV CLASS="theorem"><FONT COLOR=black><FONT SIZE=3><B>Exercise 3</B></FONT></FONT><FONT COLOR=black><FONT SIZE=3>  <EM>
| | </PRE> |
| Write a function </EM></FONT></FONT><CODE><FONT COLOR=black><FONT SIZE=3><EM>is_between(x, y, z)</EM></FONT></FONT></CODE><FONT COLOR=black><FONT SIZE=3><EM> that | | But the extra comparison is unnecessary. |
| returns </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>True</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> if </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><I>x</I> ≤ <I>y</I> ≤ <I>z</I></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> or </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>False</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> otherwise. | | <DIV CLASS="theorem">'''Exercise 3'''  '' |
| </EM></FONT></FONT></DIV><H2 CLASS="section"><A NAME="toc69"></A><A NAME="htoc77"><FONT COLOR=black><FONT SIZE=3>6.5</FONT></FONT></A><FONT COLOR=black><FONT SIZE=3>  More recursion</FONT></FONT></H2><P><A NAME="@default466"></A><FONT COLOR=black><FONT SIZE=3>
| | Write a function ''<CODE>''is_between(x, y, z)''</CODE>'' that |
| </FONT></FONT><A NAME="@default467"></A><FONT COLOR=black><FONT SIZE=3>
| | returns ''''<TT>True</TT>'''' if ''''<I>x</I> ≤ <I>y</I> ≤ <I>z</I>'''' or ''''<TT>False</TT>'''' otherwise. |
| </FONT></FONT><A NAME="@default468"></A><FONT COLOR=black><FONT SIZE=3>
| | ''</DIV>=== 6.5  More recursion === |
| </FONT></FONT><A NAME="@default469"></A><FONT COLOR=black><FONT SIZE=3>
| | |
| </FONT></FONT><A NAME="@default470"></A></P><P><FONT COLOR=black><FONT SIZE=3>We have only covered a small subset of Python, but you might
| | |
| be interested to know that this subset is a </FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>complete</EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3> | | |
| | |
| | |
| | |
| | |
| | We have only covered a small subset of Python, but you might |
| | be interested to know that this subset is a ''complete'' |
| programming language, which means that anything that can be | | programming language, which means that anything that can be |
| computed can be expressed in this language. Any program ever written | | computed can be expressed in this language. Any program ever written |
| could be rewritten using only the language features you have learned | | could be rewritten using only the language features you have learned |
| so far (actually, you would need a few commands to control devices | | so far (actually, you would need a few commands to control devices |
| like the keyboard, mouse, disks, etc., but that’s all).</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>Proving that claim is a nontrivial exercise first accomplished by Alan | | like the keyboard, mouse, disks, etc., but that’s all). |
| | |
| | Proving that claim is a nontrivial exercise first accomplished by Alan |
| Turing, one of the first computer scientists (some would argue that he | | Turing, one of the first computer scientists (some would argue that he |
| was a mathematician, but a lot of early computer scientists started as | | was a mathematician, but a lot of early computer scientists started as |
| mathematicians). Accordingly, it is known as the Turing Thesis. | | mathematicians). Accordingly, it is known as the Turing Thesis. |
| For a more complete (and accurate) discussion of the Turing Thesis, | | For a more complete (and accurate) discussion of the Turing Thesis, |
| I recommend Michael Sipser’s book </FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>Introduction to the | | I recommend Michael Sipser’s book ''Introduction to the |
| Theory of Computation</EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3>.</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>To give you an idea of what you can do with the tools you have learned | | Theory of Computation''. |
| | |
| | To give you an idea of what you can do with the tools you have learned |
| so far, we’ll evaluate a few recursively defined mathematical | | so far, we’ll evaluate a few recursively defined mathematical |
| functions. A recursive definition is similar to a circular | | functions. A recursive definition is similar to a circular |
| definition, in the sense that the definition contains a reference to | | definition, in the sense that the definition contains a reference to |
| the thing being defined. A truly circular definition is not very | | the thing being defined. A truly circular definition is not very |
| useful:</FONT></FONT></P><DL CLASS="description"><DT CLASS="dt-description"><FONT COLOR=black><FONT SIZE=3><B>frabjuous:</B></FONT></FONT></DT><DD CLASS="dd-description"><FONT COLOR=black><FONT SIZE=3> An adjective used to describe something that is frabjuous.</FONT></FONT></DD></DL><P><A NAME="@default471"></A><FONT COLOR=black><FONT SIZE=3> | | useful: |
| </FONT></FONT><A NAME="@default472"></A><FONT COLOR=black><FONT SIZE=3>
| | <DL CLASS="description"><DT CLASS="dt-description">'''frabjuous:'''</DT><DD CLASS="dd-description"> An adjective used to describe something that is frabjuous.</DD></DL> |
| </FONT></FONT><A NAME="@default473"></A></P><P><FONT COLOR=black><FONT SIZE=3>If you saw that definition in the dictionary, you might be annoyed. On
| | |
| | |
| | |
| | |
| | If you saw that definition in the dictionary, you might be annoyed. On |
| the other hand, if you looked up the definition of the factorial | | the other hand, if you looked up the definition of the factorial |
| function, denoted with the symbol </FONT></FONT><FONT COLOR=black><FONT SIZE=3>!</FONT></FONT><FONT COLOR=black><FONT SIZE=3>, you might get something like | | function, denoted with the symbol !, you might get something like |
| this:</FONT></FONT></P><TABLE CLASS="display dcenter"><TR VALIGN="middle"><TD CLASS="dcell"><TABLE CELLSPACING=6 CELLPADDING=0><TR><TD ALIGN=right NOWRAP><FONT COLOR=black><FONT SIZE=3> </FONT></FONT></TD><TD ALIGN=center NOWRAP><FONT COLOR=black><FONT SIZE=3> </FONT></FONT></TD><TD ALIGN=left NOWRAP><FONT COLOR=black><FONT SIZE=3>0! = 1 </FONT></FONT></TD></TR> | | this: |
| <TR><TD ALIGN=right NOWRAP><FONT COLOR=black><FONT SIZE=3> </FONT></FONT></TD><TD ALIGN=center NOWRAP><FONT COLOR=black><FONT SIZE=3> </FONT></FONT></TD><TD ALIGN=left NOWRAP><FONT COLOR=black><FONT SIZE=3><I>n</I>! = <I>n</I> (<I>n</I>−1)!</FONT></FONT></TD></TR> | | <TABLE CLASS="display dcenter"><TR VALIGN="middle"><TD CLASS="dcell"><TABLE CELLSPACING=6 CELLPADDING=0><TR><TD ALIGN=right NOWRAP> </TD><TD ALIGN=center NOWRAP> </TD><TD ALIGN=left NOWRAP>0! = 1 </TD></TR> |
| | <TR><TD ALIGN=right NOWRAP> </TD><TD ALIGN=center NOWRAP> </TD><TD ALIGN=left NOWRAP><I>n</I>! = <I>n</I> (<I>n</I>−1)!</TD></TR> |
| </TABLE></TD></TR> | | </TABLE></TD></TR> |
| </TABLE><P><FONT COLOR=black><FONT SIZE=3>This definition says that the factorial of 0 is 1, and the factorial | | </TABLE> |
| of any other value, </FONT></FONT><FONT COLOR=black><FONT SIZE=3><I>n</I></FONT></FONT><FONT COLOR=black><FONT SIZE=3>, is </FONT></FONT><FONT COLOR=black><FONT SIZE=3><I>n</I></FONT></FONT><FONT COLOR=black><FONT SIZE=3> multiplied by the factorial of </FONT></FONT><FONT COLOR=black><FONT SIZE=3><I>n</I>−1</FONT></FONT><FONT COLOR=black><FONT SIZE=3>.</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>So </FONT></FONT><FONT COLOR=black><FONT SIZE=3>3!</FONT></FONT><FONT COLOR=black><FONT SIZE=3> is 3 times </FONT></FONT><FONT COLOR=black><FONT SIZE=3>2!</FONT></FONT><FONT COLOR=black><FONT SIZE=3>, which is 2 times </FONT></FONT><FONT COLOR=black><FONT SIZE=3>1!</FONT></FONT><FONT COLOR=black><FONT SIZE=3>, which is 1 times | | This definition says that the factorial of 0 is 1, and the factorial |
| </FONT></FONT><FONT COLOR=black><FONT SIZE=3>0!</FONT></FONT><FONT COLOR=black><FONT SIZE=3>. Putting it all together, </FONT></FONT><FONT COLOR=black><FONT SIZE=3>3!</FONT></FONT><FONT COLOR=black><FONT SIZE=3> equals 3 times 2 times 1 times 1,
| | of any other value, <I>n</I>, is <I>n</I> multiplied by the factorial of <I>n</I>−1. |
| which is 6.</FONT></FONT></P><P><A NAME="@default474"></A><FONT COLOR=black><FONT SIZE=3> | | |
| </FONT></FONT><A NAME="@default475"></A><FONT COLOR=black><FONT SIZE=3>
| | So 3! is 3 times 2!, which is 2 times 1!, which is 1 times |
| </FONT></FONT><A NAME="@default476"></A></P><P><FONT COLOR=black><FONT SIZE=3>If you can write a recursive definition of something, you can usually
| | 0!. Putting it all together, 3! equals 3 times 2 times 1 times 1, |
| | which is 6. |
| | |
| | |
| | |
| | |
| | |
| | If you can write a recursive definition of something, you can usually |
| write a Python program to evaluate it. The first step is to decide | | write a Python program to evaluate it. The first step is to decide |
| what the parameters should be. In this case it should be clear | | what the parameters should be. In this case it should be clear |
| that </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>factorial</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> takes an integer:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def factorial(n): | | that <TT>factorial</TT> takes an integer: |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>If the argument happens to be 0, all we have to do is return 1:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def factorial(n):
| | <PRE CLASS="verbatim">def factorial(n): |
| | </PRE> |
| | If the argument happens to be 0, all we have to do is return 1: |
| | <PRE CLASS="verbatim">def factorial(n): |
| if n == 0: | | if n == 0: |
| return 1 | | return 1 |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>Otherwise, and this is the interesting part, we have to make a
| | </PRE> |
| recursive call to find the factorial of </FONT></FONT><FONT COLOR=black><FONT SIZE=3><I>n</I>−1</FONT></FONT><FONT COLOR=black><FONT SIZE=3> and then multiply it by | | Otherwise, and this is the interesting part, we have to make a |
| </FONT></FONT><FONT COLOR=black><FONT SIZE=3><I>n</I></FONT></FONT><FONT COLOR=black><FONT SIZE=3>:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def factorial(n):
| | recursive call to find the factorial of <I>n</I>−1 and then multiply it by |
| | <I>n</I>: |
| | <PRE CLASS="verbatim">def factorial(n): |
| if n == 0: | | if n == 0: |
| return 1 | | return 1 |
| Line 233: |
Line 371: |
| result = n * recurse | | result = n * recurse |
| return result | | return result |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>The flow of execution for this program is similar to the flow of </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>countdown</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> in Section </FONT></FONT><A HREF="book006.html#recursion"><FONT COLOR=black><FONT SIZE=3>5.8</FONT></FONT></A><FONT COLOR=black><FONT SIZE=3>. If we call </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>factorial</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>
| | </PRE> |
| with the value 3:</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>Since 3 is not 0, we take the second branch and calculate the factorial | | The flow of execution for this program is similar to the flow of <TT>countdown</TT> in Section 5.8. If we call <TT>factorial</TT> |
| of </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>n-1</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>...</FONT></FONT></P><BLOCKQUOTE CLASS="quote"><FONT COLOR=black><FONT SIZE=3> | | with the value 3: |
| | |
| | Since 3 is not 0, we take the second branch and calculate the factorial |
| | of <TT>n-1</TT>... |
| | <BLOCKQUOTE CLASS="quote"> |
| Since 2 is not 0, we take the second branch and calculate the factorial of | | Since 2 is not 0, we take the second branch and calculate the factorial of |
| </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>n-1</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>...</FONT></FONT><BLOCKQUOTE CLASS="quote"><FONT COLOR=black><FONT SIZE=3>
| | <TT>n-1</TT>...<BLOCKQUOTE CLASS="quote"> |
| Since 1 is not 0, we take the second branch and calculate the factorial | | Since 1 is not 0, we take the second branch and calculate the factorial |
| of </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>n-1</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>...</FONT></FONT><BLOCKQUOTE CLASS="quote"><FONT COLOR=black><FONT SIZE=3> | | of <TT>n-1</TT>...<BLOCKQUOTE CLASS="quote"> |
| Since 0 </FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>is</EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3> 0, we take the first branch and return 1 | | Since 0 ''is'' 0, we take the first branch and return 1 |
| without making any more recursive calls. | | without making any more recursive calls. |
| </FONT></FONT></BLOCKQUOTE><P><FONT COLOR=black><FONT SIZE=3>The return value (1) is multiplied by </FONT></FONT><FONT COLOR=black><FONT SIZE=3><I>n</I></FONT></FONT><FONT COLOR=black><FONT SIZE=3>, which is 1, and the
| | </BLOCKQUOTE> |
| | The return value (1) is multiplied by <I>n</I>, which is 1, and the |
| result is returned. | | result is returned. |
| </FONT></FONT></P></BLOCKQUOTE><P><FONT COLOR=black><FONT SIZE=3>The return value (1) is multiplied by </FONT></FONT><FONT COLOR=black><FONT SIZE=3><I>n</I></FONT></FONT><FONT COLOR=black><FONT SIZE=3>, which is 2, and the
| | |
| | </BLOCKQUOTE> |
| | The return value (1) is multiplied by <I>n</I>, which is 2, and the |
| result is returned. | | result is returned. |
| </FONT></FONT></P></BLOCKQUOTE><P><FONT COLOR=black><FONT SIZE=3>The return value (2) is multiplied by </FONT></FONT><FONT COLOR=black><FONT SIZE=3><I>n</I></FONT></FONT><FONT COLOR=black><FONT SIZE=3>, which is 3, and the result, 6,
| | |
| | </BLOCKQUOTE> |
| | The return value (2) is multiplied by <I>n</I>, which is 3, and the result, 6, |
| becomes the return value of the function call that started the whole | | becomes the return value of the function call that started the whole |
| process.</FONT></FONT></P><P><A NAME="@default477"></A></P><P><FONT COLOR=black><FONT SIZE=3>Here is what the stack diagram looks like for this sequence of function | | process. |
| calls:</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3><BR> | | |
| | Here is what the stack diagram looks like for this sequence of function |
| | calls: |
|
| |
|
| </FONT></FONT></P><DIV CLASS="center"><FONT COLOR=black><FONT SIZE=3><IMG SRC="book009.png"></FONT></FONT></DIV><P><FONT COLOR=black><FONT SIZE=3>
| |
| <BR> | | <BR> |
| </FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>The return values are shown being passed back up the stack. In each | | |
| frame, the return value is the value of </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>result</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>, which is the | | |
| product of </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>n</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> and </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>recurse</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>.</FONT></FONT></P><P><A NAME="@default478"></A></P><P><FONT COLOR=black><FONT SIZE=3>In the last frame, the local | | <DIV CLASS="center"><IMG SRC="book009.png"></DIV> |
| variables </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>recurse</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> and </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>result</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> do not exist, because | | |
| the branch that creates them does not execute.</FONT></FONT></P><H2 CLASS="section"><A NAME="toc70"></A><A NAME="htoc78"><FONT COLOR=black><FONT SIZE=3>6.6</FONT></FONT></A><FONT COLOR=black><FONT SIZE=3>  Leap of faith</FONT></FONT></H2><P><FONT COLOR=black><FONT SIZE=3> | | <BR> |
| </FONT></FONT><A NAME="@default479"></A><FONT COLOR=black><FONT SIZE=3>
| | |
| </FONT></FONT><A NAME="@default480"></A></P><P><FONT COLOR=black><FONT SIZE=3>Following the flow of execution is one way to read programs, but
| | |
| | The return values are shown being passed back up the stack. In each |
| | frame, the return value is the value of <TT>result</TT>, which is the |
| | product of <TT>n</TT> and <TT>recurse</TT>. |
| | |
| | In the last frame, the local |
| | variables <TT>recurse</TT> and <TT>result</TT> do not exist, because |
| | the branch that creates them does not execute. |
| | === 6.6  Leap of faith === |
| | |
| | |
| | |
| | |
| | |
| | Following the flow of execution is one way to read programs, but |
| it can quickly become labyrinthine. An | | it can quickly become labyrinthine. An |
| alternative is what I call the “leap of faith.” When you come to a | | alternative is what I call the “leap of faith.” When you come to a |
| function call, instead of following the flow of execution, you </FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>assume</EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3> that the function works correctly and returns the right | | function call, instead of following the flow of execution, you ''assume'' that the function works correctly and returns the right |
| result.</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>In fact, you are already practicing this leap of faith when you use | | result. |
| built-in functions. When you call </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>math.cos</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> or </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>math.exp</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>, | | |
| | In fact, you are already practicing this leap of faith when you use |
| | built-in functions. When you call <TT>math.cos</TT> or <TT>math.exp</TT>, |
| you don’t examine the bodies of those functions. You just | | you don’t examine the bodies of those functions. You just |
| assume that they work because the people who wrote the built-in | | assume that they work because the people who wrote the built-in |
| functions were good programmers.</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>The same is true when you call one of your own functions. For | | functions were good programmers. |
| example, in Section </FONT></FONT><A HREF="#boolean"><FONT COLOR=black><FONT SIZE=3>6.4</FONT></FONT></A><FONT COLOR=black><FONT SIZE=3>, we wrote a function called | | |
| </FONT></FONT><CODE><FONT COLOR=black><FONT SIZE=3>is_divisible</FONT></FONT></CODE><FONT COLOR=black><FONT SIZE=3> that determines whether one number is divisible by
| | The same is true when you call one of your own functions. For |
| | example, in Section 6.4, we wrote a function called |
| | <CODE>is_divisible</CODE> that determines whether one number is divisible by |
| another. Once we have convinced ourselves that this function is | | another. Once we have convinced ourselves that this function is |
| correct—by examining the code and testing—we can use the function | | correct—by examining the code and testing—we can use the function |
| without looking at the body again.</FONT></FONT></P><P><A NAME="@default481"></A></P><P><FONT COLOR=black><FONT SIZE=3>The same is true of recursive programs. When you get to the recursive | | without looking at the body again. |
| | |
| | The same is true of recursive programs. When you get to the recursive |
| call, instead of following the flow of execution, you should assume | | call, instead of following the flow of execution, you should assume |
| that the recursive call works (yields the correct result) and then ask | | that the recursive call works (yields the correct result) and then ask |
| yourself, “Assuming that I can find the factorial of </FONT></FONT><FONT COLOR=black><FONT SIZE=3><I>n</I>−1</FONT></FONT><FONT COLOR=black><FONT SIZE=3>, can I | | yourself, “Assuming that I can find the factorial of <I>n</I>−1, can I |
| compute the factorial of </FONT></FONT><FONT COLOR=black><FONT SIZE=3><I>n</I></FONT></FONT><FONT COLOR=black><FONT SIZE=3>?” In this case, it is clear that you | | compute the factorial of <I>n</I>?” In this case, it is clear that you |
| can, by multiplying by </FONT></FONT><FONT COLOR=black><FONT SIZE=3><I>n</I></FONT></FONT><FONT COLOR=black><FONT SIZE=3>.</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>Of course, it’s a bit strange to assume that the function works | | can, by multiplying by <I>n</I>. |
| | |
| | Of course, it’s a bit strange to assume that the function works |
| correctly when you haven’t finished writing it, but that’s why | | correctly when you haven’t finished writing it, but that’s why |
| it’s called a leap of faith!</FONT></FONT></P><H2 CLASS="section"><A NAME="toc71"></A><A NAME="htoc79"><FONT COLOR=black><FONT SIZE=3>6.7</FONT></FONT></A><FONT COLOR=black><FONT SIZE=3>  One more example</FONT></FONT></H2><P><FONT COLOR=black><FONT SIZE=3> | | it’s called a leap of faith! |
| </FONT></FONT><A NAME="one more example"></A></P><P><A NAME="@default482"></A><FONT COLOR=black><FONT SIZE=3>
| | === 6.7  One more example === |
| </FONT></FONT><A NAME="@default483"></A></P><P><FONT COLOR=black><FONT SIZE=3>After </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>factorial</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>, the most common example of a recursively
| | |
| defined mathematical function is </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>fibonacci</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>, which has the | | |
| following definition</FONT></FONT><SUP><A NAME="text9" HREF="#note9"><FONT COLOR=black><FONT SIZE=3>1</FONT></FONT></A></SUP><FONT COLOR=black><FONT SIZE=3>:</FONT></FONT></P><TABLE CLASS="display dcenter"><TR VALIGN="middle"><TD CLASS="dcell"><TABLE CELLSPACING=6 CELLPADDING=0><TR><TD ALIGN=right NOWRAP><FONT COLOR=black><FONT SIZE=3> </FONT></FONT></TD><TD ALIGN=center NOWRAP><FONT COLOR=black><FONT SIZE=3> </FONT></FONT></TD><TD ALIGN=left NOWRAP><FONT COLOR=black><FONT SIZE=3><I>fibonacci</I></FONT></FONT><FONT COLOR=black><FONT SIZE=3>(0) = 0 </FONT></FONT></TD></TR> | | |
| <TR><TD ALIGN=right NOWRAP><FONT COLOR=black><FONT SIZE=3> </FONT></FONT></TD><TD ALIGN=center NOWRAP><FONT COLOR=black><FONT SIZE=3> </FONT></FONT></TD><TD ALIGN=left NOWRAP><FONT COLOR=black><FONT SIZE=3><I>fibonacci</I></FONT></FONT><FONT COLOR=black><FONT SIZE=3>(1) = 1 </FONT></FONT></TD></TR> | | |
| <TR><TD ALIGN=right NOWRAP><FONT COLOR=black><FONT SIZE=3> </FONT></FONT></TD><TD ALIGN=center NOWRAP><FONT COLOR=black><FONT SIZE=3> </FONT></FONT></TD><TD ALIGN=left NOWRAP><FONT COLOR=black><FONT SIZE=3><I>fibonacci</I></FONT></FONT><FONT COLOR=black><FONT SIZE=3>(<I>n</I>) = </FONT></FONT><FONT COLOR=black><FONT SIZE=3><I>fibonacci</I></FONT></FONT><FONT COLOR=black><FONT SIZE=3>(<I>n</I>−1) + </FONT></FONT><FONT COLOR=black><FONT SIZE=3><I>fibonacci</I></FONT></FONT><FONT COLOR=black><FONT SIZE=3>(<I>n</I>−2);</FONT></FONT></TD></TR> | | |
| | |
| | |
| | After <TT>factorial</TT>, the most common example of a recursively |
| | defined mathematical function is <TT>fibonacci</TT>, which has the |
| | following definition<SUP>1</SUP>: |
| | <TABLE CLASS="display dcenter"><TR VALIGN="middle"><TD CLASS="dcell"><TABLE CELLSPACING=6 CELLPADDING=0><TR><TD ALIGN=right NOWRAP> </TD><TD ALIGN=center NOWRAP> </TD><TD ALIGN=left NOWRAP><I>fibonacci</I>(0) = 0 </TD></TR> |
| | <TR><TD ALIGN=right NOWRAP> </TD><TD ALIGN=center NOWRAP> </TD><TD ALIGN=left NOWRAP><I>fibonacci</I>(1) = 1 </TD></TR> |
| | <TR><TD ALIGN=right NOWRAP> </TD><TD ALIGN=center NOWRAP> </TD><TD ALIGN=left NOWRAP><I>fibonacci</I>(<I>n</I>) = <I>fibonacci</I>(<I>n</I>−1) + <I>fibonacci</I>(<I>n</I>−2);</TD></TR> |
| </TABLE></TD></TR> | | </TABLE></TD></TR> |
| </TABLE><P><FONT COLOR=black><FONT SIZE=3> | | </TABLE> |
| Translated into Python, it looks like this:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def fibonacci (n): | | |
| | Translated into Python, it looks like this: |
| | <PRE CLASS="verbatim">def fibonacci (n): |
| if n == 0: | | if n == 0: |
| return 0 | | return 0 |
| Line 295: |
Line 475: |
| else: | | else: |
| return fibonacci(n-1) + fibonacci(n-2) | | return fibonacci(n-1) + fibonacci(n-2) |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>If you try to follow the flow of execution here, even for fairly
| | </PRE> |
| small values of </FONT></FONT><FONT COLOR=black><FONT SIZE=3><I>n</I></FONT></FONT><FONT COLOR=black><FONT SIZE=3>, your head explodes. But according to the | | If you try to follow the flow of execution here, even for fairly |
| | small values of <I>n</I>, your head explodes. But according to the |
| leap of faith, if you assume that the two recursive calls | | leap of faith, if you assume that the two recursive calls |
| work correctly, then it is clear that you get | | work correctly, then it is clear that you get |
| the right result by adding them together.</FONT></FONT></P><P><A NAME="@default484"></A></P><H2 CLASS="section"><A NAME="toc72"></A><A NAME="htoc80"><FONT COLOR=black><FONT SIZE=3>6.8</FONT></FONT></A><FONT COLOR=black><FONT SIZE=3>  Checking types</FONT></FONT></H2><P><FONT COLOR=black><FONT SIZE=3> | | the right result by adding them together. |
| </FONT></FONT><A NAME="guardian"></A></P><P><A NAME="@default485"></A><FONT COLOR=black><FONT SIZE=3>
| | |
| </FONT></FONT><A NAME="@default486"></A><FONT COLOR=black><FONT SIZE=3>
| | === 6.8  Checking types === |
| </FONT></FONT><A NAME="@default487"></A></P><P><FONT COLOR=black><FONT SIZE=3>What happens if we call </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>factorial</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> and give it 1.5 as an argument?</FONT></FONT></P><P><A NAME="@default488"></A></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>>>> factorial(1.5)
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | What happens if we call <TT>factorial</TT> and give it 1.5 as an argument? |
| | |
| | <PRE CLASS="verbatim">>>> factorial(1.5) |
| RuntimeError: Maximum recursion depth exceeded | | RuntimeError: Maximum recursion depth exceeded |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>It looks like an infinite recursion. But how can that be? There is a
| | </PRE> |
| base case—when </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>n == 0</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3>. But if </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>n</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> is not an integer, | | It looks like an infinite recursion. But how can that be? There is a |
| we can </FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>miss</EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3> the base case and recurse forever.</FONT></FONT></P><P><A NAME="@default489"></A><FONT COLOR=black><FONT SIZE=3> | | base case—when <TT>n == 0</TT>. But if <TT>n</TT> is not an integer, |
| </FONT></FONT><A NAME="@default490"></A></P><P><FONT COLOR=black><FONT SIZE=3>In the first recursive call, the value of </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>n</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> is 0.5.
| | we can ''miss'' the base case and recurse forever. |
| | |
| | |
| | |
| | |
| | In the first recursive call, the value of <TT>n</TT> is 0.5. |
| In the next, it is -0.5. From there, it gets smaller | | In the next, it is -0.5. From there, it gets smaller |
| (more negative), but it will never be 0.</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>We have two choices. We can try to generalize the </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>factorial</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> | | (more negative), but it will never be 0. |
| function to work with floating-point numbers, or we can make </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>factorial</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> check the type of its argument. The first option is | | |
| called the gamma function</FONT></FONT><SUP><A NAME="text10" HREF="#note10"><FONT COLOR=black><FONT SIZE=3>2</FONT></FONT></A></SUP><FONT COLOR=black><FONT SIZE=3> and it’s a | | We have two choices. We can try to generalize the <TT>factorial</TT> |
| little beyond the scope of this book. So we’ll go for the second.</FONT></FONT></P><P><A NAME="@default491"></A></P><P><FONT COLOR=black><FONT SIZE=3>We can use the built-in function </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>isinstance</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> to verify the type | | function to work with floating-point numbers, or we can make <TT>factorial</TT> check the type of its argument. The first option is |
| | called the gamma function<SUP>2</SUP> and it’s a |
| | little beyond the scope of this book. So we’ll go for the second. |
| | |
| | We can use the built-in function <TT>isinstance</TT> to verify the type |
| of the argument. While we’re at it, we can also make sure the | | of the argument. While we’re at it, we can also make sure the |
| argument is positive:</FONT></FONT></P><P><A NAME="@default492"></A><FONT COLOR=black><FONT SIZE=3> | | argument is positive: |
| </FONT></FONT><A NAME="@default493"></A></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def factorial (n):
| | |
| | |
| | |
| | <PRE CLASS="verbatim">def factorial (n): |
| if not isinstance(n, int): | | if not isinstance(n, int): |
| print 'Factorial is only defined for integers.' | | print 'Factorial is only defined for integers.' |
| Line 326: |
Line 529: |
| else: | | else: |
| return n * factorial(n-1) | | return n * factorial(n-1) |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>The first base case handles nonintegers; the
| | </PRE> |
| | The first base case handles nonintegers; the |
| second catches negative integers. In both cases, the program prints | | second catches negative integers. In both cases, the program prints |
| an error message and returns </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>None</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> to indicate that something | | an error message and returns <TT>None</TT> to indicate that something |
| went wrong:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>>>> factorial('fred') | | went wrong: |
| | <PRE CLASS="verbatim">>>> factorial('fred') |
| Factorial is only defined for integers. | | Factorial is only defined for integers. |
| None | | None |
| Line 335: |
Line 540: |
| Factorial is only defined for positive integers. | | Factorial is only defined for positive integers. |
| None | | None |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>If we get past both checks, then we know that </FONT></FONT><FONT COLOR=black><FONT SIZE=3><I>n</I></FONT></FONT><FONT COLOR=black><FONT SIZE=3> is a positive
| | </PRE> |
| integer, and we can prove that the recursion terminates.</FONT></FONT></P><P><A NAME="@default494"></A><FONT COLOR=black><FONT SIZE=3> | | If we get past both checks, then we know that <I>n</I> is a positive |
| </FONT></FONT><A NAME="@default495"></A></P><P><FONT COLOR=black><FONT SIZE=3>This program demonstrates a pattern sometimes called a </FONT></FONT><FONT COLOR=black><FONT SIZE=3><B>guardian</B></FONT></FONT><FONT COLOR=black><FONT SIZE=3>.
| | integer, and we can prove that the recursion terminates. |
| | |
| | |
| | |
| | |
| | This program demonstrates a pattern sometimes called a '''guardian'''. |
| The first two conditionals act as guardians, protecting the code that | | The first two conditionals act as guardians, protecting the code that |
| follows from values that might cause an error. The guardians make it | | follows from values that might cause an error. The guardians make it |
| possible to prove the correctness of the code.</FONT></FONT></P><H2 CLASS="section"><A NAME="toc73"></A><A NAME="htoc81"><FONT COLOR=black><FONT SIZE=3>6.9</FONT></FONT></A><FONT COLOR=black><FONT SIZE=3>  Debugging</FONT></FONT></H2><P><FONT COLOR=black><FONT SIZE=3> | | possible to prove the correctness of the code. |
| </FONT></FONT><A NAME="factdebug"></A></P><P><A NAME="@default496"></A></P><P><FONT COLOR=black><FONT SIZE=3>Breaking a large program into smaller functions creates natural
| | === 6.9  Debugging === |
| | |
| | |
| | |
| | |
| | Breaking a large program into smaller functions creates natural |
| checkpoints for debugging. If a function is not working, there are | | checkpoints for debugging. If a function is not working, there are |
| three possibilities to consider:</FONT></FONT></P><UL CLASS="itemize"><LI CLASS="li-itemize"><FONT COLOR=black><FONT SIZE=3>There is something wrong with the arguments the function | | three possibilities to consider: |
| is getting; a precondition is violated.</FONT></FONT></LI><LI CLASS="li-itemize"><FONT COLOR=black><FONT SIZE=3>There is something wrong with the function; a postcondition | | |
| is violated.</FONT></FONT></LI><LI CLASS="li-itemize"><FONT COLOR=black><FONT SIZE=3>There is something wrong with the return value or the | | *There is something wrong with the arguments the function |
| way it is being used.</FONT></FONT></LI></UL><P><FONT COLOR=black><FONT SIZE=3>To rule out the first possibility, you can add a </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>print</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> statement | | is getting; a precondition is violated. |
| | |
| | *There is something wrong with the function; a postcondition |
| | is violated. |
| | |
| | *There is something wrong with the return value or the |
| | way it is being used. |
| | |
| | To rule out the first possibility, you can add a <TT>print</TT> statement |
| at the beginning of the function and display the values of the | | at the beginning of the function and display the values of the |
| parameters (and maybe their types). Or you can write code | | parameters (and maybe their types). Or you can write code |
| that checks the preconditions explicitly.</FONT></FONT></P><P><A NAME="@default497"></A><FONT COLOR=black><FONT SIZE=3> | | that checks the preconditions explicitly. |
| </FONT></FONT><A NAME="@default498"></A></P><P><FONT COLOR=black><FONT SIZE=3>If the parameters look good, add a </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>print</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> statement before each
| | |
| </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>return</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> statement that displays the return value. If
| | |
| | |
| | |
| | If the parameters look good, add a <TT>print</TT> statement before each |
| | <TT>return</TT> statement that displays the return value. If |
| possible, check the result by hand. Consider calling the | | possible, check the result by hand. Consider calling the |
| function with values that make it easy to check the result | | function with values that make it easy to check the result |
| (as in Section </FONT></FONT><A HREF="#incremental development"><FONT COLOR=black><FONT SIZE=3>6.2</FONT></FONT></A><FONT COLOR=black><FONT SIZE=3>).</FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3>If the function seems to be working, look at the function call | | (as in Section 6.2). |
| | |
| | If the function seems to be working, look at the function call |
| to make sure the return value is being used correctly (or used | | to make sure the return value is being used correctly (or used |
| at all!).</FONT></FONT></P><P><A NAME="@default499"></A></P><P><FONT COLOR=black><FONT SIZE=3>Adding print statements at the beginning and end of a function | | at all!). |
| | |
| | Adding print statements at the beginning and end of a function |
| can help make the flow of execution more visible. | | can help make the flow of execution more visible. |
| For example, here is a version of </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>factorial</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> with | | For example, here is a version of <TT>factorial</TT> with |
| print statements:</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4>def factorial(n): | | print statements: |
| | <PRE CLASS="verbatim">def factorial(n): |
| space = ' ' * (4 * n) | | space = ' ' * (4 * n) |
| print space, 'factorial', n | | print space, 'factorial', n |
| Line 370: |
Line 602: |
| print space, 'returning', result | | print space, 'returning', result |
| return result | | return result |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3><TT>space</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> is a string of space characters that controls the
| | </PRE> |
| indentation of the output. Here is the result of </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>factorial(5)</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> :</FONT></FONT></P><PRE CLASS="verbatim"><FONT COLOR=blue><FONT SIZE=4> factorial 5 | | <TT>space</TT> is a string of space characters that controls the |
| | indentation of the output. Here is the result of <TT>factorial(5)</TT> : |
| | <PRE CLASS="verbatim"> factorial 5 |
| factorial 4 | | factorial 4 |
| factorial 3 | | factorial 3 |
| Line 383: |
Line 617: |
| returning 24 | | returning 24 |
| returning 120 | | returning 120 |
| </FONT></FONT></PRE><P><FONT COLOR=black><FONT SIZE=3>If you are confused about the flow of execution, this kind of
| | </PRE> |
| | If you are confused about the flow of execution, this kind of |
| output can be helpful. It takes some time to develop effective | | output can be helpful. It takes some time to develop effective |
| scaffolding, but a little bit of scaffolding can save a lot of debugging.</FONT></FONT></P><H2 CLASS="section"><A NAME="toc74"></A><A NAME="htoc82"><FONT COLOR=black><FONT SIZE=3>6.10</FONT></FONT></A><FONT COLOR=black><FONT SIZE=3>  Glossary</FONT></FONT></H2><DL CLASS="description"><DT CLASS="dt-description"><FONT COLOR=black><FONT SIZE=3><B>temporary variable:</B></FONT></FONT></DT><DD CLASS="dd-description"><FONT COLOR=black><FONT SIZE=3> A variable used to store an intermediate value in | | scaffolding, but a little bit of scaffolding can save a lot of debugging. |
| | === 6.10  Glossary === |
| | |
| | <DL CLASS="description"><DT CLASS="dt-description">'''temporary variable:'''</DT><DD CLASS="dd-description"> A variable used to store an intermediate value in |
| a complex calculation. | | a complex calculation. |
| </FONT></FONT><A NAME="@default500"></A><FONT COLOR=black><FONT SIZE=3>
| | |
| </FONT></FONT><A NAME="@default501"></A></DD><DT CLASS="dt-description"><FONT COLOR=black><FONT SIZE=3><B>dead code:</B></FONT></FONT></DT><DD CLASS="dd-description"><FONT COLOR=black><FONT SIZE=3> Part of a program that can never be executed, often because
| | </DD><DT CLASS="dt-description">'''dead code:'''</DT><DD CLASS="dd-description"> Part of a program that can never be executed, often because |
| it appears after a </FONT></FONT><FONT COLOR=black><FONT SIZE=3><TT>return</TT></FONT></FONT><FONT COLOR=black><FONT SIZE=3> statement. | | it appears after a <TT>return</TT> statement. |
| </FONT></FONT><A NAME="@default502"></A></DD><DT CLASS="dt-description"><FONT COLOR=black><FONT SIZE=3><B><TT>None</TT></B></FONT></FONT><FONT COLOR=black><FONT SIZE=3><B>:</B></FONT></FONT></DT><DD CLASS="dd-description"><FONT COLOR=black><FONT SIZE=3> A special value returned by functions that
| | </DD><DT CLASS="dt-description">'''<TT>None</TT>'''''':'''</DT><DD CLASS="dd-description"> A special value returned by functions that |
| have no return statement or a return statement without an argument. | | have no return statement or a return statement without an argument. |
| </FONT></FONT><A NAME="@default503"></A><FONT COLOR=black><FONT SIZE=3>
| | |
| </FONT></FONT><A NAME="@default504"></A></DD><DT CLASS="dt-description"><FONT COLOR=black><FONT SIZE=3><B>incremental development:</B></FONT></FONT></DT><DD CLASS="dd-description"><FONT COLOR=black><FONT SIZE=3> A program development plan intended to
| | </DD><DT CLASS="dt-description">'''incremental development:'''</DT><DD CLASS="dd-description"> A program development plan intended to |
| avoid debugging by adding and testing only | | avoid debugging by adding and testing only |
| a small amount of code at a time. | | a small amount of code at a time. |
| </FONT></FONT><A NAME="@default505"></A></DD><DT CLASS="dt-description"><FONT COLOR=black><FONT SIZE=3><B>scaffolding:</B></FONT></FONT></DT><DD CLASS="dd-description"><FONT COLOR=black><FONT SIZE=3> Code that is used during program development but is
| | </DD><DT CLASS="dt-description">'''scaffolding:'''</DT><DD CLASS="dd-description"> Code that is used during program development but is |
| not part of the final version. | | not part of the final version. |
| </FONT></FONT><A NAME="@default506"></A></DD><DT CLASS="dt-description"><FONT COLOR=black><FONT SIZE=3><B>guardian:</B></FONT></FONT></DT><DD CLASS="dd-description"><FONT COLOR=black><FONT SIZE=3> A programming pattern that uses a conditional
| | </DD><DT CLASS="dt-description">'''guardian:'''</DT><DD CLASS="dd-description"> A programming pattern that uses a conditional |
| statement to check for and handle circumstances that | | statement to check for and handle circumstances that |
| might cause an error. | | might cause an error. |
| </FONT></FONT><A NAME="@default507"></A><FONT COLOR=black><FONT SIZE=3>
| | |
| </FONT></FONT><A NAME="@default508"></A></DD></DL><H2 CLASS="section"><A NAME="toc75"></A><A NAME="htoc83"><FONT COLOR=black><FONT SIZE=3>6.11</FONT></FONT></A><FONT COLOR=black><FONT SIZE=3>  Exercises</FONT></FONT></H2><DIV CLASS="theorem"><FONT COLOR=black><FONT SIZE=3><B>Exercise 4</B></FONT></FONT><FONT COLOR=black><FONT SIZE=3>  <EM>
| | </DD></DL>=== 6.11  Exercises === |
| </EM></FONT></FONT><A NAME="@default509"></A><P><FONT COLOR=black><FONT SIZE=3><EM>Draw a stack diagram for the following
| | |
| program. What does the program print?</EM></FONT></FONT></P><PRE CLASS="verbatim"><EM><FONT COLOR=blue><FONT SIZE=4>def b(z): | | <DIV CLASS="theorem">'''Exercise 4'''  '' |
| | '' |
| | ''Draw a stack diagram for the following |
| | program. What does the program print?'' |
| | <PRE CLASS="verbatim">''def b(z): |
| prod = a(z, z) | | prod = a(z, z) |
| print z, prod | | print z, prod |
| Line 421: |
Line 663: |
| y = x + 1 | | y = x + 1 |
| print c(x, y+3, x+y) | | print c(x, y+3, x+y) |
| </FONT></FONT></EM></PRE></DIV><DIV CLASS="theorem"><FONT COLOR=black><FONT SIZE=3><B>Exercise 5</B></FONT></FONT><FONT COLOR=black><FONT SIZE=3>  <EM>
| | ''</PRE></DIV><DIV CLASS="theorem">'''Exercise 5'''  '' |
| </EM></FONT></FONT><A NAME="@default510"></A><FONT COLOR=black><FONT SIZE=3><EM>
| | '''' |
| </EM></FONT></FONT><A NAME="@default511"></A><P><FONT COLOR=black><FONT SIZE=3><EM>The Ackermann function, </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><I>A</I>(<I>m</I>, <I>n</I>)</EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> is defined</EM></FONT></FONT><SUP><A NAME="text11" HREF="#note11"><FONT COLOR=black><FONT SIZE=3><EM>3</EM></FONT></FONT></A></SUP><FONT COLOR=black><FONT SIZE=3><EM>:</EM></FONT></FONT></P><TABLE CLASS="display dcenter"><TR VALIGN="middle"><TD CLASS="dcell"><FONT COLOR=black><FONT SIZE=3><EM>
| | '' |
| | | ''The Ackermann function, ''''<I>A</I>(<I>m</I>, <I>n</I>)'''' is defined''<SUP>''3''</SUP>'':'' |
| | <TABLE CLASS="display dcenter"><TR VALIGN="middle"><TD CLASS="dcell">'' |
|
| |
|
|       | |       |
|
| |
|
| </EM></FONT></FONT></TD><TD CLASS="dcell"><TABLE CELLSPACING=6 CELLPADDING=0><TR><TD ALIGN=right NOWRAP><TABLE CLASS="display"><TR VALIGN="middle"><TD CLASS="dcell"><FONT COLOR=black><FONT SIZE=3><EM><I>A</I>(<I>m</I>, <I>n</I>) = </EM></FONT></FONT></TD><TD CLASS="dcell"><TABLE CLASS="display"><TR VALIGN="middle"><TD CLASS="dcell"><FONT COLOR=black><FONT SIZE=3><EM>⎧<BR>
| | ''</TD><TD CLASS="dcell"><TABLE CELLSPACING=6 CELLPADDING=0><TR><TD ALIGN=right NOWRAP><TABLE CLASS="display"><TR VALIGN="middle"><TD CLASS="dcell">''<I>A</I>(<I>m</I>, <I>n</I>) = ''</TD><TD CLASS="dcell"><TABLE CLASS="display"><TR VALIGN="middle"><TD CLASS="dcell">''⎧<BR> |
| ⎪<BR> | | ⎪<BR> |
| ⎨<BR> | | ⎨<BR> |
| ⎪<BR> | | ⎪<BR> |
| ⎩</EM></FONT></FONT></TD><TD CLASS="dcell"><TABLE CELLSPACING=6 CELLPADDING=0><TR><TD ALIGN=left NOWRAP><FONT COLOR=black><FONT SIZE=3><EM>              <I>n</I>+1</EM></FONT></FONT></TD><TD ALIGN=left NOWRAP><FONT COLOR=black><FONT SIZE=3><EM>if </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> <I>m</I> = 0 </EM></FONT></FONT></TD></TR> | | ⎩''</TD><TD CLASS="dcell"><TABLE CELLSPACING=6 CELLPADDING=0><TR><TD ALIGN=left NOWRAP>''              <I>n</I>+1''</TD><TD ALIGN=left NOWRAP>''if '''' <I>m</I> = 0 ''</TD></TR> |
| <TR><TD ALIGN=left NOWRAP><FONT COLOR=black><FONT SIZE=3><EM>        <I>A</I>(<I>m</I>−1, 1)</EM></FONT></FONT></TD><TD ALIGN=left NOWRAP><FONT COLOR=black><FONT SIZE=3><EM>if </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> <I>m</I> > 0 </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> and </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> <I>n</I> = 0 </EM></FONT></FONT></TD></TR> | | <TR><TD ALIGN=left NOWRAP>''        <I>A</I>(<I>m</I>−1, 1)''</TD><TD ALIGN=left NOWRAP>''if '''' <I>m</I> > 0 '''' and '''' <I>n</I> = 0 ''</TD></TR> |
| <TR><TD ALIGN=left NOWRAP><FONT COLOR=black><FONT SIZE=3><EM><I>A</I>(<I>m</I>−1, <I>A</I>(<I>m</I>, <I>n</I>−1))</EM></FONT></FONT></TD><TD ALIGN=left NOWRAP><FONT COLOR=black><FONT SIZE=3><EM>if </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> <I>m</I> > 0 </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> and </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> <I>n</I> > 0.</EM></FONT></FONT></TD></TR> | | <TR><TD ALIGN=left NOWRAP>''<I>A</I>(<I>m</I>−1, <I>A</I>(<I>m</I>, <I>n</I>−1))''</TD><TD ALIGN=left NOWRAP>''if '''' <I>m</I> > 0 '''' and '''' <I>n</I> > 0.''</TD></TR> |
| </TABLE></TD></TR> | | </TABLE></TD></TR> |
| </TABLE></TD></TR> | | </TABLE></TD></TR> |
| </TABLE></TD><TD ALIGN=center NOWRAP><FONT COLOR=black><FONT SIZE=3><EM> </EM></FONT></FONT></TD><TD ALIGN=left NOWRAP><FONT COLOR=black><FONT SIZE=3><EM> </EM></FONT></FONT></TD><TD ALIGN=right NOWRAP><FONT COLOR=black><FONT SIZE=3><EM>    (1)</EM></FONT></FONT></TD></TR> | | </TABLE></TD><TD ALIGN=center NOWRAP>'' ''</TD><TD ALIGN=left NOWRAP>'' ''</TD><TD ALIGN=right NOWRAP>''    (1)''</TD></TR> |
| </TABLE></TD></TR> | | </TABLE></TD></TR> |
| </TABLE><P><FONT COLOR=black><FONT SIZE=3><EM> | | </TABLE> |
| Write a function named </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>ack</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> that evaluates Ackerman’s function. | | '' |
| Use your function to evaluate </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>ack(3, 4)</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>, which should be 125. | | Write a function named ''''<TT>ack</TT>'''' that evaluates Ackerman’s function. |
| What happens for larger values of </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>m</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> and </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>n</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>?</EM></FONT></FONT></P></DIV><DIV CLASS="theorem"><FONT COLOR=black><FONT SIZE=3><B>Exercise 6</B></FONT></FONT><FONT COLOR=black><FONT SIZE=3>  <EM> | | Use your function to evaluate ''''<TT>ack(3, 4)</TT>'''', which should be 125. |
| </EM></FONT></FONT><A NAME="palindrome"></A><P><A NAME="@default512"></A></P><P><FONT COLOR=black><FONT SIZE=3><EM>A palindrome is a word that is spelled the same backward and
| | What happens for larger values of ''''<TT>m</TT>'''' and ''''<TT>n</TT>''''?'' |
| | </DIV><DIV CLASS="theorem">'''Exercise 6'''  '' |
| | '' |
| | |
| | ''A palindrome is a word that is spelled the same backward and |
| forward, like “noon” and “redivider”. Recursively, a word | | forward, like “noon” and “redivider”. Recursively, a word |
| is a palindrome if the first and last letters are the same | | is a palindrome if the first and last letters are the same |
| and the middle is a palindrome.</EM></FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3><EM>The following are functions that take a string argument and | | and the middle is a palindrome.'' |
| return the first, last, and middle letters:</EM></FONT></FONT></P><PRE CLASS="verbatim"><EM><FONT COLOR=blue><FONT SIZE=4>def first(word): | | |
| | ''The following are functions that take a string argument and |
| | return the first, last, and middle letters:'' |
| | <PRE CLASS="verbatim">''def first(word): |
| return word[0] | | return word[0] |
|
| |
|
| Line 455: |
Line 705: |
| def middle(word): | | def middle(word): |
| return word[1:-1] | | return word[1:-1] |
| </FONT></FONT></EM></PRE><P><EM><FONT COLOR=black><FONT SIZE=3>We’ll see how they work in Chapter </FONT></FONT></EM><A HREF="book009.html#strings"><EM><FONT COLOR=black><FONT SIZE=3>8</FONT></FONT></EM></A><EM><FONT COLOR=black><FONT SIZE=3>.</FONT></FONT></EM></P><OL CLASS="enumerate" type=1><LI CLASS="li-enumerate"><EM><FONT COLOR=black><FONT SIZE=3>Type these functions into a file named </FONT></FONT></EM><EM><FONT COLOR=black><FONT SIZE=3><TT>palindrome.py</TT></FONT></FONT></EM><EM><FONT COLOR=black><FONT SIZE=3>
| | ''</PRE> |
| and test them out. What happens if you call </FONT></FONT></EM><EM><FONT COLOR=black><FONT SIZE=3><TT>middle</TT></FONT></FONT></EM><EM><FONT COLOR=black><FONT SIZE=3> with | | ''We’ll see how they work in Chapter ''''8''''.'' |
| | |
| | *''Type these functions into a file named ''''<TT>palindrome.py</TT>'''' |
| | and test them out. What happens if you call ''''<TT>middle</TT>'''' with |
| a string with two letters? One letter? What about the empty | | a string with two letters? One letter? What about the empty |
| string, which is written </FONT></FONT></EM><CODE><EM><FONT COLOR=black><FONT SIZE=3>''</FONT></FONT></EM></CODE><EM><FONT COLOR=black><FONT SIZE=3> and contains no letters?</FONT></FONT></EM></LI><LI CLASS="li-enumerate"><EM><FONT COLOR=black><FONT SIZE=3>Write a function called </FONT></FONT></EM><CODE><EM><FONT COLOR=black><FONT SIZE=3>is_palindrome</FONT></FONT></EM></CODE><EM><FONT COLOR=black><FONT SIZE=3> that takes | | string, which is written ''<CODE>''''''</CODE>'' and contains no letters?'' |
| a string argument and returns </FONT></FONT></EM><EM><FONT COLOR=black><FONT SIZE=3><TT>True</TT></FONT></FONT></EM><EM><FONT COLOR=black><FONT SIZE=3> if it is a palindrome | | |
| and </FONT></FONT></EM><EM><FONT COLOR=black><FONT SIZE=3><TT>False</TT></FONT></FONT></EM><EM><FONT COLOR=black><FONT SIZE=3> otherwise. Remember that you can use the | | *''Write a function called ''<CODE>''is_palindrome''</CODE>'' that takes |
| built-in function </FONT></FONT></EM><EM><FONT COLOR=black><FONT SIZE=3><TT>len</TT></FONT></FONT></EM><EM><FONT COLOR=black><FONT SIZE=3> to check the length of a string.</FONT></FONT></EM></LI></OL></DIV><DIV CLASS="theorem"><FONT COLOR=black><FONT SIZE=3><B>Exercise 7</B></FONT></FONT><FONT COLOR=black><FONT SIZE=3>  <EM> | | a string argument and returns ''''<TT>True</TT>'''' if it is a palindrome |
| A number, </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><I>a</I></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>, is a power of </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><I>b</I></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> if it is divisible by </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><I>b</I></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> | | and ''''<TT>False</TT>'''' otherwise. Remember that you can use the |
| and </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><I>a</I>/<I>b</I></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> is a power of </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><I>b</I></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>. Write a function called | | built-in function ''''<TT>len</TT>'''' to check the length of a string.'' |
| </EM></FONT></FONT><CODE><FONT COLOR=black><FONT SIZE=3><EM>is_power</EM></FONT></FONT></CODE><FONT COLOR=black><FONT SIZE=3><EM> that takes parameters </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>a</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> and </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>b</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>
| | |
| and returns </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>True</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> if </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>a</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> is a power of </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>b</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>. | | </DIV><DIV CLASS="theorem">'''Exercise 7'''  '' |
| </EM></FONT></FONT></DIV><DIV CLASS="theorem"><FONT COLOR=black><FONT SIZE=3><B>Exercise 8</B></FONT></FONT><FONT COLOR=black><FONT SIZE=3>  </FONT></FONT><P><A NAME="@default513"></A><FONT COLOR=black><FONT SIZE=3><EM>
| | A number, ''''<I>a</I>'''', is a power of ''''<I>b</I>'''' if it is divisible by ''''<I>b</I>'''' |
| </EM></FONT></FONT><A NAME="@default514"></A></P><P><FONT COLOR=black><FONT SIZE=3><EM>The greatest common divisor (GCD) of </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><I>a</I></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> and </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><I>b</I></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> is the largest number
| | and ''''<I>a</I>/<I>b</I>'''' is a power of ''''<I>b</I>''''. Write a function called |
| that divides both of them with no remainder</EM></FONT></FONT><SUP><A NAME="text12" HREF="#note12"><FONT COLOR=black><FONT SIZE=3><EM>4</EM></FONT></FONT></A></SUP><FONT COLOR=black><FONT SIZE=3><EM>.</EM></FONT></FONT></P><P><FONT COLOR=black><FONT SIZE=3><EM>One way to find the GCD of two numbers is Euclid’s algorithm, | | ''<CODE>''is_power''</CODE>'' that takes parameters ''''<TT>a</TT>'''' and ''''<TT>b</TT>'''' |
| which is based on the observation that if </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><I>r</I></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> is the remainder | | and returns ''''<TT>True</TT>'''' if ''''<TT>a</TT>'''' is a power of ''''<TT>b</TT>''''. |
| when </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><I>a</I></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> is divided by </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><I>b</I></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>, then </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><I>gcd</I>(<I>a</I>, <I>b</I>) = <I>gcd</I>(<I>b</I>, <I>r</I>)</EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>. | | ''</DIV><DIV CLASS="theorem">'''Exercise 8'''   |
| As a base case, we can consider </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><I>gcd</I>(<I>a</I>, 0) = <I>a</I></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>.</EM></FONT></FONT></P><P><A NAME="@default515"></A><FONT COLOR=black><FONT SIZE=3><EM> | | '' |
| </EM></FONT></FONT><A NAME="@default516"></A></P><P><FONT COLOR=black><FONT SIZE=3><EM>Write a function called
| | '' |
| </EM></FONT></FONT><CODE><FONT COLOR=black><FONT SIZE=3><EM>gcd</EM></FONT></FONT></CODE><FONT COLOR=black><FONT SIZE=3><EM> that takes parameters </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>a</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM> and </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>b</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>
| | |
| | ''The greatest common divisor (GCD) of ''''<I>a</I>'''' and ''''<I>b</I>'''' is the largest number |
| | that divides both of them with no remainder''<SUP>''4''</SUP>''.'' |
| | |
| | ''One way to find the GCD of two numbers is Euclid’s algorithm, |
| | which is based on the observation that if ''''<I>r</I>'''' is the remainder |
| | when ''''<I>a</I>'''' is divided by ''''<I>b</I>'''', then ''''<I>gcd</I>(<I>a</I>, <I>b</I>) = <I>gcd</I>(<I>b</I>, <I>r</I>)''''. |
| | As a base case, we can consider ''''<I>gcd</I>(<I>a</I>, 0) = <I>a</I>''''.'' |
| | |
| | '' |
| | '' |
| | |
| | ''Write a function called |
| | ''<CODE>''gcd''</CODE>'' that takes parameters ''''<TT>a</TT>'''' and ''''<TT>b</TT>'''' |
| and returns their greatest common divisor. If you need | | and returns their greatest common divisor. If you need |
| help, see </EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM><TT>wikipedia.org/wiki/Euclidean_algorithm</TT></EM></FONT></FONT><FONT COLOR=black><FONT SIZE=3><EM>.</EM></FONT></FONT></P></DIV><HR CLASS="footnoterule"><DL CLASS="thefootnotes"><DT CLASS="dt-thefootnotes"><FONT COLOR=black><FONT SIZE=3> | | help, see ''''<TT>wikipedia.org/wiki/Euclidean_algorithm</TT>''''.'' |
| </FONT></FONT><A NAME="note9" HREF="#text9"><FONT COLOR=black><FONT SIZE=3>1</FONT></FONT></A></DT><DD CLASS="dd-thefootnotes"><FONT COLOR=black><FONT SIZE=3>See
| | </DIV><HR CLASS="footnoterule"><DL CLASS="thefootnotes"><DT CLASS="dt-thefootnotes"> |
| | 1</DT><DD CLASS="dd-thefootnotes">See |
| <TT>wikipedia.org/wiki/Fibonacci_number</TT>. | | <TT>wikipedia.org/wiki/Fibonacci_number</TT>. |
| </FONT></FONT></DD><DT CLASS="dt-thefootnotes"><A NAME="note10" HREF="#text10"><FONT COLOR=black><FONT SIZE=3>2</FONT></FONT></A></DT><DD CLASS="dd-thefootnotes"><FONT COLOR=black><FONT SIZE=3>See
| | </DD><DT CLASS="dt-thefootnotes">2</DT><DD CLASS="dd-thefootnotes">See |
| <TT>wikipedia.org/wiki/Gamma_function</TT>. | | <TT>wikipedia.org/wiki/Gamma_function</TT>. |
| </FONT></FONT></DD><DT CLASS="dt-thefootnotes"><A NAME="note11" HREF="#text11"><FONT COLOR=black><FONT SIZE=3>3</FONT></FONT></A></DT><DD CLASS="dd-thefootnotes"><FONT COLOR=black><FONT SIZE=3>See
| | </DD><DT CLASS="dt-thefootnotes">3</DT><DD CLASS="dd-thefootnotes">See |
| <TT>wikipedia.org/wiki/Ackermann_function</TT> | | <TT>wikipedia.org/wiki/Ackermann_function</TT> |
| </FONT></FONT></DD><DT CLASS="dt-thefootnotes"><A NAME="note12" HREF="#text12"><FONT COLOR=black><FONT SIZE=3>4</FONT></FONT></A></DT><DD CLASS="dd-thefootnotes"><FONT COLOR=black><FONT SIZE=3>This exercise is
| | </DD><DT CLASS="dt-thefootnotes">4</DT><DD CLASS="dd-thefootnotes">This exercise is |
| based on an example from Abelson and Sussman’s <EM>Structure and | | based on an example from Abelson and Sussman’s ''Structure and |
| Interpretation of Computer Programs</EM>. | | Interpretation of Computer Programs''. |
| </FONT></FONT></DD></DL>
| | </DD></DL> |
| <HR> | | <HR> |
| <A HREF="book006.html"><IMG SRC="previous_motif.gif" ALT="Previous"></A>
| | <IMG SRC="previous_motif.gif" ALT="Previous"> |
| <A HREF="index.html"><IMG SRC="contents_motif.gif" ALT="Up"></A>
| | <IMG SRC="contents_motif.gif" ALT="Up"> |
| <A HREF="book008.html"><IMG SRC="next_motif.gif" ALT="Next"></A>
| | <IMG SRC="next_motif.gif" ALT="Next"> |
| </BODY>
| |
| </HTML>
| |