pensepython.github.io/07-iteration.html at master · PensePython/pensepython.github.io

History

493 lines (474 loc) · 30.3 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"

"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<head>

<title>Iteration — Pense Python 2e documentation</title>

var DOCUMENTATION_OPTIONS = {

URL_ROOT: './',

VERSION: '2e',

COLLAPSE_INDEX: false,

FILE_SUFFIX: '.html',

HAS_SOURCE: true

};

</script>

</head>

<h1>Iteration<a class="headerlink" href="#iteration" title="Permalink to this headline">¶</a></h1>

<p>This chapter is about iteration, which is the ability to run a block of

statements repeatedly. We saw a kind of iteration, using recursion, in

Section [recursion]. We saw another kind, using a for loop, in

Section [repetition]. In this chapter we’ll see yet another kind, using

a while statement. But first I want to say a little more about variable

assignment.</p>

<h2>Reassignment<a class="headerlink" href="#reassignment" title="Permalink to this headline">¶</a></h2>

<p>As you may have discovered, it is legal to make more than one assignment

to the same variable. A new assignment makes an existing variable refer

to a new value (and stop referring to the old value).</p>

</pre></div>

</div>

<p>The first time we display x, its value is 5; the second time, its value

is 7.</p>

<p>Figure [fig.assign2] shows what <strong>reassignment</strong> looks like in a state

diagram.</p>

<p>At this point I want to address a common source of confusion. Because

Python uses the equal sign (=) for assignment, it is tempting to

interpret a statement like a = b as a mathematical proposition of

equality; that is, the claim that a and b are equal. But this

interpretation is wrong.</p>

<p>First, equality is a symmetric relationship and assignment is not. For

example, in mathematics, if <span class="math">a=7</span> then <span class="math">7=a</span>. But in Python,

the statement a = 7 is legal and 7 = a is not.</p>

<p>Also, in mathematics, a proposition of equality is either true or false

for all time. If <span class="math">a=b</span> now, then <span class="math">a</span> will always equal

<span class="math">b</span>. In Python, an assignment statement can make two variables

equal, but they don’t have to stay that way:</p>

<span class="gp">>>> </span><span class="n">b</span> <span class="o">=</span> <span class="n">a</span> <span class="c"># a and b are now equal</span>

<span class="gp">>>> </span><span class="n">a</span> <span class="o">=</span> <span class="mi">3</span> <span class="c"># a and b are no longer equal</span>

</pre></div>

</div>

<p>The third line changes the value of a but does not change the value of

b, so they are no longer equal.</p>

<p>Reassigning variables is often useful, but you should use it with

caution. If the values of variables change frequently, it can make the

code difficult to read and debug.</p>

<p class="caption"><span class="caption-text">State diagram.</span></p>

</div>

<h2>Updating variables<a class="headerlink" href="#updating-variables" title="Permalink to this headline">¶</a></h2>

<p>A common kind of reassignment is an <strong>update</strong>, where the new value of

the variable depends on the old.</p>

</pre></div>

</div>

<p>This means “get the current value of x, add one, and then update x with

the new value.”</p>

<p>If you try to update a variable that doesn’t exist, you get an error,

because Python evaluates the right side before it assigns a value to x:</p>

<span class="go">NameError: name 'x' is not defined</span>

</pre></div>

</div>

<p>Before you can update a variable, you have to <strong>initialize</strong> it, usually

with a simple assignment:</p>

</pre></div>

</div>

<p>Updating a variable by adding 1 is called an <strong>increment</strong>; subtracting

1 is called a <strong>decrement</strong>.</p>

</div>

<h2>The while statement<a class="headerlink" href="#the-while-statement" title="Permalink to this headline">¶</a></h2>

<p>Computers are often used to automate repetitive tasks. Repeating

identical or similar tasks without making errors is something that

computers do well and people do poorly. In a computer program,

repetition is also called <strong>iteration</strong>.</p>

<p>We have already seen two functions, countdown and <code class="docutils literal"><span class="pre">print_n</span></code>, that

iterate using recursion. Because iteration is so common, Python provides

language features to make it easier. One is the for statement we saw in

Section [repetition]. We’ll get back to that later.</p>

<p>Another is the while statement. Here is a version of countdown that uses

a while statement:</p>

<div class="highlight-python"><div class="highlight"><pre><span class="k">def</span> <span class="nf">countdown</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>

<span class="k">while</span> <span class="n">n</span> <span class="o">></span> <span class="mi">0</span><span class="p">:</span>

<span class="k">print</span><span class="p">(</span><span class="n">n</span><span class="p">)</span>

<span class="k">print</span><span class="p">(</span><span class="s">'Blastoff!'</span><span class="p">)</span>

</pre></div>

</div>

<p>You can almost read the while statement as if it were English. It means,

“While n is greater than 0, display the value of n and then decrement n.

When you get to 0, display the word Blastoff!”</p>

<p>More formally, here is the flow of execution for a while statement:</p>

<li>Determine whether the condition is true or false.</li>

<li>If false, exit the while statement and continue execution at the next

statement.</li>

<li>If the condition is true, run the body and then go back to step 1.</li>

</ol>

<p>This type of flow is called a loop because the third step loops back

around to the top.</p>

<p>The body of the loop should change the value of one or more variables so

that the condition becomes false eventually and the loop terminates.

Otherwise the loop will repeat forever, which is called an <strong>infinite

loop</strong>. An endless source of amusement for computer scientists is the

observation that the directions on shampoo, “Lather, rinse, repeat”, are

an infinite loop.</p>

<p>In the case of countdown, we can prove that the loop terminates: if n is

zero or negative, the loop never runs. Otherwise, n gets smaller each

time through the loop, so eventually we have to get to 0.</p>

<p>For some other loops, it is not so easy to tell. For example:</p>

<div class="highlight-python"><div class="highlight"><pre><span class="k">def</span> <span class="nf">sequence</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>

<span class="k">while</span> <span class="n">n</span> <span class="o">!=</span> <span class="mi">1</span><span class="p">:</span>

<span class="k">print</span><span class="p">(</span><span class="n">n</span><span class="p">)</span>

</pre></div>

</div>

<p>The condition for this loop is n != 1, so the loop will continue until n

is 1, which makes the condition false.</p>

<p>Each time through the loop, the program outputs the value of n and then

checks whether it is even or odd. If it is even, n is divided by 2. If

it is odd, the value of n is replaced with n*3 + 1. For example, if the

argument passed to sequence is 3, the resulting values of n are 3, 10,

5, 16, 8, 4, 2, 1.</p>

<p>Since n sometimes increases and sometimes decreases, there is no obvious

proof that n will ever reach 1, or that the program terminates. For some

particular values of n, we can prove termination. For example, if the

starting value is a power of two, n will be even every time through the

loop until it reaches 1. The previous example ends with such a sequence,

starting with 16.</p>

<p>The hard question is whether we can prove that this program terminates

for <em>all</em> positive values of n. So far, no one has been able to prove it

<em>or</em> disprove it! (See <a class="reference external" href="http://en.wikipedia.org/wiki/Collatz_conjecture">http://en.wikipedia.org/wiki/Collatz_conjecture</a>.)</p>

<p>As an exercise, rewrite the function <code class="docutils literal"><span class="pre">print_n</span></code> from

Section [recursion] using iteration instead of recursion.</p>

</div>

<h2>break<a class="headerlink" href="#break" title="Permalink to this headline">¶</a></h2>

<p>Sometimes you don’t know it’s time to end a loop until you get half way

through the body. In that case you can use the break statement to jump

out of the loop.</p>

<p>For example, suppose you want to take input from the user until they

type done. You could write:</p>

<div class="highlight-python"><div class="highlight"><pre><span class="k">while</span> <span class="bp">True</span><span class="p">:</span>

<span class="n">line</span> <span class="o">=</span> <span class="nb">input</span><span class="p">(</span><span class="s">'> '</span><span class="p">)</span>

<span class="k">break</span>

<span class="k">print</span><span class="p">(</span><span class="n">line</span><span class="p">)</span>

<span class="k">print</span><span class="p">(</span><span class="s">'Done!'</span><span class="p">)</span>

</pre></div>

</div>

<p>The loop condition is True, which is always true, so the loop runs until

it hits the break statement.</p>

<p>Each time through, it prompts the user with an angle bracket. If the

user types done, the break statement exits the loop. Otherwise the

program echoes whatever the user types and goes back to the top of the

loop. Here’s a sample run:</p>

<div class="highlight-python"><div class="highlight"><pre>> not done

not done

> done

Done!

</pre></div>

</div>

<p>This way of writing while loops is common because you can check the

condition anywhere in the loop (not just at the top) and you can express

the stop condition affirmatively (“stop when this happens”) rather than

negatively (“keep going until that happens”).</p>

</div>

<h2>Square roots<a class="headerlink" href="#square-roots" title="Permalink to this headline">¶</a></h2>

<p>Loops are often used in programs that compute numerical results by

starting with an approximate answer and iteratively improving it.</p>

<p>For example, one way of computing square roots is Newton’s method.

Suppose that you want to know the square root of <span class="math">a</span>. If you start

with almost any estimate, <span class="math">x</span>, you can compute a better estimate

with the following formula:</p>

</div><p>For example, if <span class="math">a</span> is 4 and <span class="math">x</span> is 3:</p>

</pre></div>

</div>

<p>The result is closer to the correct answer (<span class="math">\sqrt{4} = 2</span>). If we

repeat the process with the new estimate, it gets even closer:</p>

</pre></div>

</div>

<p>After a few more updates, the estimate is almost exact:</p>

</pre></div>

</div>

<p>In general we don’t know ahead of time how many steps it takes to get to

the right answer, but we know when we get there because the estimate

stops changing:</p>

</pre></div>

</div>

<p>When y == x, we can stop. Here is a loop that starts with an initial

estimate, x, and improves it until it stops changing:</p>

<div class="highlight-python"><div class="highlight"><pre><span class="k">while</span> <span class="bp">True</span><span class="p">:</span>

<span class="k">print</span><span class="p">(</span><span class="n">x</span><span class="p">)</span>

<span class="k">break</span>

</pre></div>

</div>

<p>For most values of a this works fine, but in general it is dangerous to

test float equality. Floating-point values are only approximately right:

most rational numbers, like <span class="math">1/3</span>, and irrational numbers, like

<span class="math">\sqrt{2}</span>, can’t be represented exactly with a float.</p>

<p>Rather than checking whether x and y are exactly equal, it is safer to

use the built-in function abs to compute the absolute value, or

magnitude, of the difference between them:</p>

<div class="highlight-python"><div class="highlight"><pre><span class="k">if</span> <span class="nb">abs</span><span class="p">(</span><span class="n">y</span><span class="o">-</span><span class="n">x</span><span class="p">)</span> <span class="o"><</span> <span class="n">epsilon</span><span class="p">:</span>

<span class="k">break</span>

</pre></div>

</div>

<p>Where <code class="docutils literal"><span class="pre">epsilon</span></code> has a value like 0.0000001 that determines how close

is close enough.</p>

</div>

<h2>Algorithms<a class="headerlink" href="#algorithms" title="Permalink to this headline">¶</a></h2>

<p>Newton’s method is an example of an <strong>algorithm</strong>: it is a mechanical

process for solving a category of problems (in this case, computing

square roots).</p>

<p>To understand what an algorithm is, it might help to start with

something that is not an algorithm. When you learned to multiply

single-digit numbers, you probably memorized the multiplication table.

In effect, you memorized 100 specific solutions. That kind of knowledge

is not algorithmic.</p>

<p>But if you were “lazy”, you might have learned a few tricks. For

example, to find the product of <span class="math">n</span> and 9, you can write

<span class="math">n-1</span> as the first digit and <span class="math">10-n</span> as the second digit.

This trick is a general solution for multiplying any single-digit number

by 9. That’s an algorithm!</p>

<p>Similarly, the techniques you learned for addition with carrying,

subtraction with borrowing, and long division are all algorithms. One of

the characteristics of algorithms is that they do not require any

intelligence to carry out. They are mechanical processes where each step

follows from the last according to a simple set of rules.</p>

<p>Executing algorithms is boring, but designing them is interesting,

intellectually challenging, and a central part of computer science.</p>

<p>Some of the things that people do naturally, without difficulty or

conscious thought, are the hardest to express algorithmically.

Understanding natural language is a good example. We all do it, but so

far no one has been able to explain <em>how</em> we do it, at least not in the

form of an algorithm.</p>

</div>

<h2>Debugging<a class="headerlink" href="#debugging" title="Permalink to this headline">¶</a></h2>

<p>As you start writing bigger programs, you might find yourself spending

more time debugging. More code means more chances to make an error and

more places for bugs to hide.</p>

<p>One way to cut your debugging time is “debugging by bisection”. For

example, if there are 100 lines in your program and you check them one

at a time, it would take 100 steps.</p>

<p>Instead, try to break the problem in half. Look at the middle of the

program, or near it, for an intermediate value you can check. Add a

print statement (or something else that has a verifiable effect) and run

the program.</p>

<p>If the mid-point check is incorrect, there must be a problem in the

first half of the program. If it is correct, the problem is in the

second half.</p>

<p>Every time you perform a check like this, you halve the number of lines

you have to search. After six steps (which is fewer than 100), you would

be down to one or two lines of code, at least in theory.</p>

<p>In practice it is not always clear what the “middle of the program” is

and not always possible to check it. It doesn’t make sense to count

lines and find the exact midpoint. Instead, think about places in the

program where there might be errors and places where it is easy to put a

check. Then choose a spot where you think the chances are about the same

that the bug is before or after the check.</p>

</div>

<span id="glossary07"></span><h2>Glossary<a class="headerlink" href="#glossary" title="Permalink to this headline">¶</a></h2>

<dt>reatribuição (<em>reassignment</em>)</dt>

<dd>Assigning a new value to a variable that already exists.</dd>

<dt>atualização (<em>update</em>)</dt>

<dd>An assignment where the new value of the variable depends on the old.</dd>

<dt>inicialização (<em>initialization</em>)</dt>

<dd>An assignment that gives an initial value to a variable that will be updated.</dd>

<dt>incrementar (<em>increment</em>)</dt>

<dd>An update that increases the value of a variable (often by one).</dd>

<dt>decrementar (<em>decrement</em>)</dt>

<dd>An update that decreases the value of a variable.</dd>

<dt>iteração (<em>iteration</em>)</dt>

<dd>Repeated execution of a set of statements using either a recursive function call or a loop.</dd>

<dt>laço infinito (<em>infinite loop</em>)</dt>

<dd>A loop in which the terminating condition is never satisfied.</dd>

<dt>algoritmo (<em>algorithm</em>)</dt>

<dd>A general process for solving a category of problems.</dd>

</dl>

</div>

<h2>Exercises<a class="headerlink" href="#exercises" title="Permalink to this headline">¶</a></h2>

<p>Copy the loop from Section [squareroot] and encapsulate it in a function

called <code class="docutils literal"><span class="pre">mysqrt</span></code> that takes a as a parameter, chooses a reasonable

value of x, and returns an estimate of the square root of a.</p>

<p>To test it, write a function named <code class="docutils literal"><span class="pre">test_square_root</span></code> that prints a

table like this:</p>

<div class="highlight-python"><div class="highlight"><pre>a mysqrt(a) math.sqrt(a) diff

- --------- ------------ ----

1.0 1.0 1.0 0.0

2.0 1.41421356237 1.41421356237 2.22044604925e-16

3.0 1.73205080757 1.73205080757 0.0

4.0 2.0 2.0 0.0

5.0 2.2360679775 2.2360679775 0.0

6.0 2.44948974278 2.44948974278 0.0

7.0 2.64575131106 2.64575131106 0.0

8.0 2.82842712475 2.82842712475 4.4408920985e-16

9.0 3.0 3.0 0.0

</pre></div>

</div>

<p>The first column is a number, <span class="math">a</span>; the second column is the square

root of <span class="math">a</span> computed with <code class="docutils literal"><span class="pre">mysqrt</span></code>; the third column is the

square root computed by math.sqrt; the fourth column is the absolute

value of the difference between the two estimates.</p>

<p>The built-in function eval takes a string and evaluates it using the

Python interpreter. For example:</p>

<span class="gp">>>> </span><span class="kn">import</span> <span class="nn">math</span>

</pre></div>

</div>

<p>Write a function called <code class="docutils literal"><span class="pre">eval_loop</span></code> that iteratively prompts the user,

takes the resulting input and evaluates it using eval, and prints the

result.</p>

<p>It should continue until the user enters <code class="docutils literal"><span class="pre">'done'</span></code>, and then return the

value of the last expression it evaluated.</p>

<p>The mathematician Srinivasa Ramanujan found an infinite series that can

be used to generate a numerical approximation of <span class="math">1 / \pi</span>:</p>

<p><span class="math">\frac{1}{\pi} = \frac{2\sqrt{2}}{9801}

\sum^\infty_{k=0} \frac{(4k)!(1103+26390k)}{(k!)^4 396^{4k}}</span></p>

</div><p>Write a function called <code class="docutils literal"><span class="pre">estimate_pi</span></code> that uses this formula to

compute and return an estimate of <span class="math">\pi</span>. It should use a while

loop to compute terms of the summation until the last term is smaller

than 1e-15 (which is Python notation for <span class="math">10^{-15}</span>). You can

check the result by comparing it to math.pi.</p>

<p>Solution: <a class="reference external" href="http://thinkpython2.com/code/pi.py">http://thinkpython2.com/code/pi.py</a>.</p>

</div>

<h3><a href="index.html">Table Of Contents</a></h3>

<ul>

<li><a class="reference internal" href="#">Iteration</a><ul>

<li><a class="reference internal" href="#reassignment">Reassignment</a></li>

<li><a class="reference internal" href="#updating-variables">Updating variables</a></li>

<li><a class="reference internal" href="#the-while-statement">The while statement</a></li>

<li><a class="reference internal" href="#break">break</a></li>

<li><a class="reference internal" href="#square-roots">Square roots</a></li>

<li><a class="reference internal" href="#algorithms">Algorithms</a></li>

<li><a class="reference internal" href="#debugging">Debugging</a></li>

<li><a class="reference internal" href="#glossary">Glossary</a></li>

<li><a class="reference internal" href="#exercises">Exercises</a></li>

</ul>

</li>

</ul>

<h3>Related Topics</h3>

<ul>

<li><a href="index.html">Documentation overview</a><ul>

<li>Previous: <a href="06-fruitful-fn.html" title="previous chapter">Fruitful functions</a></li>

<li>Next: <a href="08-string.html" title="next chapter">Strings</a></li>

</ul></li>

</ul>

</div>

<li><a href="_sources/07-iteration.txt"

rel="nofollow">Show Source</a></li>

</ul>

</div>

<h3>Quick search</h3>

</form>

Enter search terms or a module, class or function name.

</p>

</div>

</div>

</div>

& <a href="https://github.com/bitprophet/alabaster">Alabaster 0.7.6</a>

<a href="_sources/07-iteration.txt"

rel="nofollow">Page source</a>

</div>

</body>

</html>

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

FilesExpand file tree

07-iteration.html

Latest commit

History

07-iteration.html

File metadata and controls