📄 page_1121.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <title>page_1121</title> <link rel="stylesheet" href="reset.css" type="text/css" media="all"> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> </head> <body> <table summary="top nav" border="0" width="100%"> <tr> <td align="left" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_1120.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_1121</strong></td> <td align="right" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_1122.html">next page ></a></td> </tr> <tr> <td align="left" colspan="3" style="background: #ffffff; padding: 20px;"> <table border="0" width="100%" cellpadding="0"><tr><td align="center"> <table border="0" cellpadding="2" cellspacing="0" width="100%"><tr><td align="left"></td> <td align="right"></td> </tr></table></td></tr><tr><td align="left"><p></p><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="right"><font face="Times New Roman, Times, Serif" size="2" color="#FF0000">Page 1121</font></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3"><img src="50bed68f1cd159d616d24afe03c6f128.gif" border="0" alt="1121-01.gif" width="172" height="50" /></font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">or even as</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3"><img src="c1ef9e2cd6ecf80ce2a728c464d8d312.gif" border="0" alt="1121-02.gif" width="200" height="56" /></font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">In fact, we can write the formula most concisely as</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3"><img src="3376ff1111f9c05a05c051c5037ba0be.gif" border="0" alt="1121-03.gif" width="84" height="16" /></font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">This definition of <i>X</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>N</sup></font></i><font face="Times New Roman, Times, Serif" size="2"><sup></sup></font><font face="Times New Roman, Times, Serif" size="3"> is a classic recursive definitionthat is, a definition given in terms of a smaller version of itself.</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td rowspan="5"><img src="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" border="0" width="96" height="1" alt="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" /></td> <td colspan="3" height="12"></td> <td rowspan="5"><img src="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" border="0" width="96" height="1" alt="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" /></td></tr><tr><td colspan="3" height="2"><table cellpadding="0" cellspacing="0" border="0"><tr><td></td></tr></table></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="2">Recursive Definition A definition in which something is defined in terms of smaller versions of itself.</font></td><td></td></tr><tr><td colspan="3" height="2"><table cellpadding="0" cellspacing="0" border="0"><tr><td></td></tr></table></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3"><i>X</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>N</sup></font></i><font face="Times New Roman, Times, Serif" size="2"><sup></sup></font><font face="Times New Roman, Times, Serif" size="3"> is defined in terms of multiplying <i>X</i> times <i>X</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>N-1</sup></font><font face="Times New Roman, Times, Serif" size="3">.</font></i><font face="Times New Roman, Times, Serif" size="3"> How is <i>X</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>N-1</sup></font></i><font face="Times New Roman, Times, Serif" size="2"><sup></sup></font><font face="Times New Roman, Times, Serif" size="3"> defined? Why, as <i>X * X</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>N-2</sup></font><font face="Times New Roman, Times, Serif" size="3">,</font></i><font face="Times New Roman, Times, Serif" size="3"> of course! And <i>X</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>N-2</sup></font></i><font face="Times New Roman, Times, Serif" size="2"><sup></sup></font><font face="Times New Roman, Times, Serif" size="3"> is <i>X * X</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>N-3</sup></font><font face="Times New Roman, Times, Serif" size="3">;</font></i><font face="Times New Roman, Times, Serif" size="3"> <i>X</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>N-3</sup></font></i><font face="Times New Roman, Times, Serif" size="2"><sup></sup></font><font face="Times New Roman, Times, Serif" size="3"> is <i>X * X</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>N-4</sup></font><font face="Times New Roman, Times, Serif" size="3">;</font></i><font face="Times New Roman, Times, Serif" size="3"> and so on. In this example, in terms of smaller versions of itself means that the exponent is decremented each time.</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">When does the process stop? When we have reached a case where we know the answer without resorting to a recursive definition. In this example, it is the case where <i>N</i> equals 1: <i>X</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>1</sup></font></i><font face="Times New Roman, Times, Serif" size="2"><sup></sup></font><font face="Times New Roman, Times, Serif" size="3"> is <i>X.</i> The case (or cases) for which an answer is explicitly known is called the base case. The case for which the solution is expressed in terms of a smaller version of itself is called the recursive or general case. A recursive algorithm is an algorithm that expresses the solution in terms of a call to itself, a recursive call. A recursive algorithm must terminate; that is, it must have a base case.</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td rowspan="5"><img src="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" border="0" width="96" height="1" alt="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" /></td> <td colspan="3" height="12"></td> <td rowspan="5"><img src="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" border="0" width="96" height="1" alt="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" /></td></tr><tr><td colspan="3" height="2"><table cellpadding="0" cellspacing="0" border="0"><tr><td></td></tr></table></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="2">Base Case The case for which the solution can be stated nonrecursively.</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"><img src="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" border="0" width="96" height="1" alt="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" /></td> <td colspan="3" height="12"></td> <td rowspan="5"><img src="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" border="0" width="96" height="1" alt="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" /></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="2">General Case The case for which the solution is expressed in terms of a smaller version of itself; also known as <i>recursive case.</i></font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td rowspan="5"><img src="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" border="0" width="96" height="1" alt="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" /></td> <td colspan="3" height="12"></td> <td rowspan="5"><img src="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" border="0" width="96" height="1" alt="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" /></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="2">Recursive Algorithm A solution that is expressed in terms of (a) smaller instances of itself and (b) a base case.</font></td><td></td></tr><tr><td colspan="3" height="2"><table cellpadding="0" cellspacing="0" border="0"><tr><td></td></tr></table></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">Figure 19-1 shows a recursive version of the </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">Power</font><font face="Times New Roman, Times, Serif" size="3"> function with the base case and the recursive call marked. The function is embedded in a program that reads in a number and an exponent and prints the result.</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td></tr></table><p><font size="0"></font></p>聽 </td> </tr> <tr> <td align="left" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_1120.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_1121</strong></td> <td align="right" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_1122.html">next page ></a></td> </tr> </table> </body> </html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -