pensepython.github.io/05-cond-recur.html at master · PensePython/pensepython.github.io

History

705 lines (686 loc) · 45.2 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

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

525

526

527

528

529

530

531

532

533

534

535

536

537

538

539

540

541

542

543

544

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569

570

571

572

573

574

575

576

577

578

579

580

581

582

583

584

585

586

587

588

589

590

591

592

593

594

595

596

597

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638

639

640

641

642

643

644

645

646

647

648

649

650

651

652

653

654

655

656

657

658

659

660

661

662

663

664

665

666

667

668

669

670

671

672

673

674

675

676

677

678

679

680

681

682

683

684

685

686

687

688

689

690

691

692

693

694

695

696

697

698

699

700

701

702

703

704

705

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

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

<head>

<title>Conditionals and recursion — Pense Python 2e documentation</title>

var DOCUMENTATION_OPTIONS = {

URL_ROOT: './',

VERSION: '2e',

COLLAPSE_INDEX: false,

FILE_SUFFIX: '.html',

HAS_SOURCE: true

};

</script>

</head>

<h1>Conditionals and recursion<a class="headerlink" href="#conditionals-and-recursion" title="Permalink to this headline">¶</a></h1>

The main topic of this chapter is the if statement, which executes

different code depending on the state of the program. But first I want

to introduce two new operators: floor division and modulus.

<h2>Floor division and modulus<a class="headerlink" href="#floor-division-and-modulus" title="Permalink to this headline">¶</a></h2>

The floor division operator, <code class="docutils literal">//</code>, divides two numbers and rounds

down to an integer. For example, suppose the run time of a movie is 105

minutes. You might want to know how long that is in hours. Conventional

division returns a floating-point number:

<div class="highlight-python"><div class="highlight"><pre>>>> minutes = 105

>>> minutes / 60

1.75

</pre></div>

</div>

But we don’t normally write hours with decimal points. Floor division

returns the integer number of hours, dropping the fraction part:

<div class="highlight-python"><div class="highlight"><pre>>>> minutes = 105

>>> hours = minutes // 60

>>> hours

1

</pre></div>

</div>

To get the remainder, you could subtract off one hour in minutes:

<div class="highlight-python"><div class="highlight"><pre>>>> remainder = minutes - hours * 60

>>> remainder

45

</pre></div>

</div>

An alternative is to use the modulus operator, <code class="docutils literal">%</code>, which divides

two numbers and returns the remainder.

>>> remainder

45

</pre></div>

</div>

The modulus operator is more useful than it seems. For example, you can

check whether one number is divisible by another—if x % y is zero, then

x is divisible by y.

Also, you can extract the right-most digit or digits from a number. For

example, x % 10 yields the right-most digit of x (in base 10). Similarly

x % 100 yields the last two digits.

If you are using Python 2, division works differently. The division

operator, <code class="docutils literal">/</code>, performs floor division if both operands are integers,

and floating-point division if either operand is a float.

</div>

<h2>Boolean expressions<a class="headerlink" href="#boolean-expressions" title="Permalink to this headline">¶</a></h2>

A boolean expression is an expression that is either true or false.

The following examples use the operator ==, which compares two operands

and produces True if they are equal and False otherwise:

<div class="highlight-python"><div class="highlight"><pre>>>> 5 == 5

True

>>> 5 == 6

False

</pre></div>

</div>

True and False are special values that belong to the type bool; they are

not strings:

<div class="highlight-python"><div class="highlight"><pre>>>> type(True)

>>> type(False)

</pre></div>

</div>

The == operator is one of the relational operators; the others are:

<div class="highlight-python"><div class="highlight"><pre>x != y # x is not equal to y

x > y # x is greater than y

x < y # x is less than y

x >= y # x is greater than or equal to y

x <= y # x is less than or equal to y

</pre></div>

</div>

Although these operations are probably familiar to you, the Python

symbols are different from the mathematical symbols. A common error is

to use a single equal sign (=) instead of a double equal sign (==).

Remember that = is an assignment operator and == is a relational

operator. There is no such thing as =< or =>.

</div>

<h2>Logical operators<a class="headerlink" href="#logical-operators" title="Permalink to this headline">¶</a></h2>

There are three logical operators: and, or, and not. The semantics

(meaning) of these operators is similar to their meaning in English. For

example, x > 0 and x < 10 is true only if x is greater than 0 and less

than 10.

n%2 == 0 or n%3 == 0 is true if either or both of the conditions is

true, that is, if the number is divisible by 2 or 3.

Finally, the not operator negates a boolean expression, so not (x > y)

is true if x > y is false, that is, if x is less than or equal to y.

Strictly speaking, the operands of the logical operators should be

boolean expressions, but Python is not very strict. Any nonzero number

is interpreted as True:

<div class="highlight-python"><div class="highlight"><pre>>>> 42 and True

True

</pre></div>

</div>

This flexibility can be useful, but there are some subtleties to it that

might be confusing. You might want to avoid it (unless you know what you

are doing).

</div>

<h2>Conditional execution<a class="headerlink" href="#conditional-execution" title="Permalink to this headline">¶</a></h2>

In order to write useful programs, we almost always need the ability to

check conditions and change the behavior of the program accordingly.

Conditional statements give us this ability. The simplest form is

the if statement:

<div class="highlight-python"><div class="highlight"><pre>if x > 0:

print('x is positive')

</pre></div>

</div>

The boolean expression after if is called the condition. If it is

true, the indented statement runs. If not, nothing happens.

if statements have the same structure as function definitions: a header

followed by an indented body. Statements like this are called compound

statements.

There is no limit on the number of statements that can appear in the

body, but there has to be at least one. Occasionally, it is useful to

have a body with no statements (usually as a place keeper for code you

haven’t written yet). In that case, you can use the pass statement,

which does nothing.

<div class="highlight-python"><div class="highlight"><pre>if x < 0:

pass # TODO: need to handle negative values!

</pre></div>

</div>

<h2>Alternative execution<a class="headerlink" href="#alternative-execution" title="Permalink to this headline">¶</a></h2>

A second form of the if statement is “alternative execution”, in which

there are two possibilities and the condition determines which one runs.

The syntax looks like this:

<div class="highlight-python"><div class="highlight"><pre>if x % 2 == 0:

print('x is even')

else:

print('x is odd')

</pre></div>

</div>

If the remainder when x is divided by 2 is 0, then we know that x is

even, and the program displays an appropriate message. If the condition

is false, the second set of statements runs. Since the condition must be

true or false, exactly one of the alternatives will run. The

alternatives are called branches, because they are branches in the

flow of execution.

</div>

<h2>Chained conditionals<a class="headerlink" href="#chained-conditionals" title="Permalink to this headline">¶</a></h2>

Sometimes there are more than two possibilities and we need more than

two branches. One way to express a computation like that is a chained

conditional:

<div class="highlight-python"><div class="highlight"><pre>if x < y:

print('x is less than y')

elif x > y:

print('x is greater than y')

else:

print('x and y are equal')

</pre></div>

</div>

elif is an abbreviation of “else if”. Again, exactly one branch will

run. There is no limit on the number of elif statements. If there is an

else clause, it has to be at the end, but there doesn’t have to be one.

<div class="highlight-python"><div class="highlight"><pre>if choice == 'a':

draw_a()

elif choice == 'b':

draw_b()

elif choice == 'c':

draw_c()

</pre></div>

</div>

Each condition is checked in order. If the first is false, the next is

checked, and so on. If one of them is true, the corresponding branch

runs and the statement ends. Even if more than one condition is true,

only the first true branch runs.

</div>

<h2>Nested conditionals<a class="headerlink" href="#nested-conditionals" title="Permalink to this headline">¶</a></h2>

One conditional can also be nested within another. We could have written

the example in the previous section like this:

<div class="highlight-python"><div class="highlight"><pre>if x == y:

print('x and y are equal')

else:

if x < y:

print('x is less than y')

else:

print('x is greater than y')

</pre></div>

</div>

The outer conditional contains two branches. The first branch contains a

simple statement. The second branch contains another if statement, which

has two branches of its own. Those two branches are both simple

statements, although they could have been conditional statements as

well.

Although the indentation of the statements makes the structure apparent,

nested conditionals become difficult to read very quickly. It is a

good idea to avoid them when you can.

Logical operators often provide a way to simplify nested conditional

statements. For example, we can rewrite the following code using a

single conditional:

<div class="highlight-python"><div class="highlight"><pre>if 0 < x:

if x < 10:

print('x is a positive single-digit number.')

</pre></div>

</div>

The print statement runs only if we make it past both conditionals, so

we can get the same effect with the and operator:

<div class="highlight-python"><div class="highlight"><pre>if 0 < x and x < 10:

print('x is a positive single-digit number.')

</pre></div>

</div>

For this kind of condition, Python provides a more concise option:

<div class="highlight-python"><div class="highlight"><pre>if 0 < x < 10:

print('x is a positive single-digit number.')

</pre></div>

</div>

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

It is legal for one function to call another; it is also legal for a

function to call itself. It may not be obvious why that is a good thing,

but it turns out to be one of the most magical things a program can do.

For example, look at the following function:

<div class="highlight-python"><div class="highlight"><pre>def countdown(n):

if n <= 0:

print('Blastoff!')

else:

print(n)

countdown(n-1)

</pre></div>

</div>

If n is 0 or negative, it outputs the word, “Blastoff!” Otherwise, it

outputs n and then calls a function named countdown—itself—passing n-1

as an argument.

What happens if we call this function like this?

<div class="highlight-python"><div class="highlight"><pre>>>> countdown(3)

</pre></div>

</div>

The execution of countdown begins with n=3, and since n is greater than

0, it outputs the value 3, and then calls itself...

<div>The execution of countdown begins with n=2, and since n is greater

than 0, it outputs the value 2, and then calls itself...

<div>The execution of countdown begins with n=1, and since n is

greater than 0, it outputs the value 1, and then calls itself...

<div>The execution of countdown begins with n=0, and since n is

not greater than 0, it outputs the word, “Blastoff!” and

then returns.</div></blockquote>

The countdown that got n=1 returns.

</div></blockquote>

The countdown that got n=2 returns.

</div></blockquote>

The countdown that got n=3 returns.

And then you’re back in <code class="docutils literal">__main__</code>. So, the total output looks like

this:

<div class="highlight-python"><div class="highlight"><pre>3

Blastoff!

</pre></div>

</div>

A function that calls itself is recursive; the process of executing

it is called recursion.

As another example, we can write a function that prints a string n

times.

<div class="highlight-python"><div class="highlight"><pre>def print_n(s, n):

if n <= 0:

return

print(s)

print_n(s, n-1)

</pre></div>

</div>

If n <= 0 the return statement exits the function. The flow of

execution immediately returns to the caller, and the remaining lines of

the function don’t run.

The rest of the function is similar to countdown: it displays s and then

calls itself to display s n-1 additional times. So the number of

lines of output is 1 + (n - 1), which adds up to n.

For simple examples like this, it is probably easier to use a for loop.

But we will see examples later that are hard to write with a for loop

and easy to write with recursion, so it is good to start early.

</div>

<h2>Stack diagrams for recursive functions<a class="headerlink" href="#stack-diagrams-for-recursive-functions" title="Permalink to this headline">¶</a></h2>

In Section [stackdiagram], we used a stack diagram to represent the

state of a program during a function call. The same kind of diagram can

help interpret a recursive function.

Every time a function gets called, Python creates a frame to contain the

function’s local variables and parameters. For a recursive function,

there might be more than one frame on the stack at the same time.

Figure [fig.stack2] shows a stack diagram for countdown called with n =

3.

Stack diagram.

</div>

As usual, the top of the stack is the frame for <code class="docutils literal">__main__</code>. It is

empty because we did not create any variables in <code class="docutils literal">__main__</code> or pass

any arguments to it.

The four countdown frames have different values for the parameter n. The

bottom of the stack, where n=0, is called the base case. It does not

make a recursive call, so there are no more frames.

As an exercise, draw a stack diagram for <code class="docutils literal">print_n</code> called with

<code class="docutils literal">s = 'Hello'</code> and n=2. Then write a function called <code class="docutils literal">do_n</code> that

takes a function object and a number, n, as arguments, and that calls

the given function n times.

</div>

<h2>Infinite recursion<a class="headerlink" href="#infinite-recursion" title="Permalink to this headline">¶</a></h2>

If a recursion never reaches a base case, it goes on making recursive

calls forever, and the program never terminates. This is known as

infinite recursion, and it is generally not a good idea. Here is a

minimal program with an infinite recursion:

<div class="highlight-python"><div class="highlight"><pre>def recurse():

recurse()

</pre></div>

</div>

In most programming environments, a program with infinite recursion does

not really run forever. Python reports an error message when the maximum

recursion depth is reached:

<div class="highlight-python"><div class="highlight"><pre> File "<stdin>", line 2, in recurse

File "<stdin>", line 2, in recurse

RuntimeError: Maximum recursion depth exceeded

</pre></div>

</div>

This traceback is a little bigger than the one we saw in the previous

chapter. When the error occurs, there are 1000 recurse frames on the

stack!

If you write encounter an infinite recursion by accident, review your

function to confirm that there is a base case that does not make a

recursive call. And if there is a base case, check whether you are

guaranteed to reach it.

</div>

<h2>Keyboard input<a class="headerlink" href="#keyboard-input" title="Permalink to this headline">¶</a></h2>

The programs we have written so far accept no input from the user. They

just do the same thing every time.

Python provides a built-in function called input that stops the program

and waits for the user to type something. When the user presses Return

or Enter, the program resumes and <code class="docutils literal">input</code> returns what the user typed

as a string. In Python 2, the same function is called <code class="docutils literal">raw_input</code>.

<div class="highlight-python"><div class="highlight"><pre>>>> text = input()

What are you waiting for?

>>> text

What are you waiting for?

</pre></div>

</div>

Before getting input from the user, it is a good idea to print a prompt

telling the user what to type. <code class="docutils literal">input</code> can take a prompt as an

argument:

<div class="highlight-python"><div class="highlight"><pre>>>> name = input('What...is your name?\n')

What...is your name?

Arthur, King of the Britons!

>>> name

Arthur, King of the Britons!

</pre></div>

</div>

The sequence <code class="docutils literal">\n</code> at the end of the prompt represents a newline,

which is a special character that causes a line break. That’s why the

user’s input appears below the prompt.

If you expect the user to type an integer, you can try to convert the

return value to int:

<div class="highlight-python"><div class="highlight"><pre>>>> prompt = 'What...is the airspeed velocity of an unladen swallow?\n'

>>> speed = input(prompt)

What...is the airspeed velocity of an unladen swallow?

42

>>> int(speed)

42

</pre></div>

</div>

But if the user types something other than a string of digits, you get

an error:

<div class="highlight-python"><div class="highlight"><pre>>>> speed = input(prompt)

What...is the airspeed velocity of an unladen swallow?

What do you mean, an African or a European swallow?

>>> int(speed)

ValueError: invalid literal for int() with base 10

</pre></div>

</div>

We will see how to handle this kind of error later.

</div>

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

When a syntax or runtime error occurs, the error message contains a lot

of information, but it can be overwhelming. The most useful parts are

usually:

<li>What kind of error it was, and</li>

<li>Where it occurred.</li>

</ul>

Syntax errors are usually easy to find, but there are a few gotchas.

Whitespace errors can be tricky because spaces and tabs are invisible

and we are used to ignoring them.

<div class="highlight-python"><div class="highlight"><pre>>>> x = 5

>>> y = 6

File "<stdin>", line 1

y = 6

^

IndentationError: unexpected indent

</pre></div>

</div>

In this example, the problem is that the second line is indented by one

space. But the error message points to y, which is misleading. In

general, error messages indicate where the problem was discovered, but

the actual error might be earlier in the code, sometimes on a previous

line.

The same is true of runtime errors. Suppose you are trying to compute a

signal-to-noise ratio in decibels. The formula is

SNR_{db} = 10 \log_{10} (P_{signal} / P_{noise}). In Python, you

might write something like this:

<div class="highlight-python"><div class="highlight"><pre>import math

signal_power = 9

noise_power = 10

ratio = signal_power // noise_power

decibels = 10 * math.log10(ratio)

print(decibels)

</pre></div>

</div>

When you run this program, you get an exception:

<div class="highlight-python"><div class="highlight"><pre>Traceback (most recent call last):

File "snr.py", line 5, in ?

decibels = 10 * math.log10(ratio)

ValueError: math domain error

</pre></div>

</div>

The error message indicates line 5, but there is nothing wrong with that

line. To find the real error, it might be useful to print the value of

ratio, which turns out to be 0. The problem is in line 4, which uses

floor division instead of floating-point division.

You should take the time to read error messages carefully, but don’t

assume that everything they say is correct.

</div>

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

<dt>divisão pelo piso (floor division)</dt>

<dd>An operator, denoted //, that divides two numbers and rounds down (toward zero) to an integer.</dd>

<dt>operador de módulo (modulus operator)</dt>

<dd>An operator, denoted with a percent sign (%), that works on integers and returns the remainder when one number is divided by another.</dd>

<dt>expressão booleana (boolean expression)</dt>

<dd>An expression whose value is either True or False.</dd>

<dt>operador relacional (relational operator)</dt>

<dd>One of the operators that compares its operands: ==, !=, >, <, >=, and <=.</dd>

<dt>operador lógico (logical operator)</dt>

<dd>One of the operators that combines boolean expressions: and, or, and not.</dd>

<dt>instrução condicional (conditional statement)</dt>

<dd>A statement that controls the flow of execution depending on some condition.</dd>

<dt>condição (condition)</dt>

<dd>The boolean expression in a conditional statement that determines which branch runs.</dd>

<dt>instrução composta (compound statement)</dt>

<dd>A statement that consists of a header and a body. The header ends with a colon (:). The body is indented relative to the header.</dd>

<dt>desvio (branch)</dt>

<dd>One of the alternative sequences of statements in a conditional statement.</dd>

<dt>condicional encadeado (chained conditional)</dt>

<dd>A conditional statement with a series of alternative branches.</dd>

<dt>condicional aninhado (nested conditional)</dt>

<dd>A conditional statement that appears in one of the branches of another conditional statement.</dd>

<dt><code class="docutils literal">return</code>, instrução (<code class="docutils literal">return</code> statement)</dt>

<dd>A statement that causes a function to end immediately and return to the caller.</dd>

<dt>recursão (recursion)</dt>

<dd>The process of calling the function that is currently executing.</dd>

<dd>A conditional branch in a recursive function that does not make a recursive call.</dd>

<dt>recursão infinita (infinite recursion)</dt>

<dd>A recursion that doesn’t have a base case, or never reaches it. Eventually, an infinite recursion causes a runtime error.</dd>

</dl>

</div>

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

The time module provides a function, also named time, that returns the

current Greenwich Mean Time in “the epoch”, which is an arbitrary time

used as a reference point. On UNIX systems, the epoch is 1 January 1970.

<div class="highlight-python"><div class="highlight"><pre>>>> import time

>>> time.time()

1437746094.5735958

</pre></div>

</div>

Write a script that reads the current time and converts it to a time of

day in hours, minutes, and seconds, plus the number of days since the

epoch.

Fermat’s Last Theorem says that there are no positive integers

a, b, and c such that

a^n + b^n = c^n

</div>for any values of n greater than 2.

<li>Write a function named <code class="docutils literal">check_fermat</code> that takes four parameters—a,

b, c and n—and checks to see if Fermat’s theorem holds. If n

is greater than 2 and

a^n + b^n = c^n

</div>the program should print, “Holy smokes, Fermat was wrong!” Otherwise

the program should print, “No, that doesn’t work.”

</li>

<li>Write a function that prompts the user to input values for a, b, c

and n, converts them to integers, and uses <code class="docutils literal">check_fermat</code> to check

whether they violate Fermat’s theorem.

</li>

</ol>

If you are given three sticks, you may or may not be able to arrange

them in a triangle. For example, if one of the sticks is 12 inches long

and the other two are one inch long, you will not be able to get the

short sticks to meet in the middle. For any three lengths, there is a

simple test to see if it is possible to form a triangle:

<div>If any of the three lengths is greater than the sum of the other

two, then you cannot form a triangle. Otherwise, you can. (If the

sum of two lengths equals the third, they form what is called a

“degenerate” triangle.)</div></blockquote>

<li>Write a function named <code class="docutils literal">is_triangle</code> that takes three integers as

arguments, and that prints either “Yes” or “No”, depending on whether

you can or cannot form a triangle from sticks with the given lengths.</li>

<li>Write a function that prompts the user to input three stick lengths,

converts them to integers, and uses <code class="docutils literal">is_triangle</code> to check whether

sticks with the given lengths can form a triangle.</li>

</ol>

What is the output of the following program? Draw a stack diagram that

shows the state of the program when it prints the result.

<div class="highlight-python"><div class="highlight"><pre>def recurse(n, s):

if n == 0:

print(s)

else:

recurse(n-1, n+s)

recurse(3, 0)

</pre></div>

</div>

<li>What would happen if you called this function like this: recurse(-1,

0)?</li>

<li>Write a docstring that explains everything someone would need to know

in order to use this function (and nothing else).</li>

</ol>

The following exercises use the turtle module, described in

Chapter [turtlechap]:

Read the following function and see if you can figure out what it does.

Then run it (see the examples in Chapter [turtlechap]).

<div class="highlight-python"><div class="highlight"><pre>def draw(t, length, n):

if n == 0:

return

angle = 50

t.fd(length*n)

t.lt(angle)

draw(t, length, n-1)

t.rt(2*angle)

t.lt(angle)

t.bk(length*n)

</pre></div>

</div>

A Koch curve.

</div>

The Koch curve is a fractal that looks something like Figure [fig.koch].

To draw a Koch curve with length x, all you have to do is

<li>Draw a Koch curve with length x/3.</li>

<li>Turn left 60 degrees.</li>

<li>Draw a Koch curve with length x/3.</li>

<li>Turn right 120 degrees.</li>

<li>Draw a Koch curve with length x/3.</li>

<li>Turn left 60 degrees.</li>

<li>Draw a Koch curve with length x/3.</li>

</ol>

The exception is if x is less than 3: in that case, you can just

draw a straight line with length x.

<li>Write a function called koch that takes a turtle and a length as

parameters, and that uses the turtle to draw a Koch curve with the

given length.

</li>

<li>Write a function called snowflake that draws three Koch curves to

make the outline of a snowflake.

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

</li>

<li>The Koch curve can be generalized in several ways. See

<a class="reference external" href="http://en.wikipedia.org/wiki/Koch_snowflake">http://en.wikipedia.org/wiki/Koch_snowflake</a> for examples and

implement your favorite.

</li>

</ol>

</div>

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

<ul>

<li><a class="reference internal" href="#">Conditionals and recursion</a><ul>

<li><a class="reference internal" href="#floor-division-and-modulus">Floor division and modulus</a></li>

<li><a class="reference internal" href="#boolean-expressions">Boolean expressions</a></li>

<li><a class="reference internal" href="#logical-operators">Logical operators</a></li>

<li><a class="reference internal" href="#conditional-execution">Conditional execution</a></li>

<li><a class="reference internal" href="#alternative-execution">Alternative execution</a></li>

<li><a class="reference internal" href="#chained-conditionals">Chained conditionals</a></li>

<li><a class="reference internal" href="#nested-conditionals">Nested conditionals</a></li>

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

<li><a class="reference internal" href="#stack-diagrams-for-recursive-functions">Stack diagrams for recursive functions</a></li>

<li><a class="reference internal" href="#infinite-recursion">Infinite recursion</a></li>

<li><a class="reference internal" href="#keyboard-input">Keyboard input</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="04-case-ui.html" title="previous chapter">Case study: interface design</a></li>

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

</ul></li>

</ul>

</div>

<li><a href="_sources/05-cond-recur.txt"

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

</ul>

</div>

<h3>Quick search</h3>

</form>

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

</div>

</div>

</div>

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

<a href="_sources/05-cond-recur.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

05-cond-recur.html

Latest commit

History

05-cond-recur.html

File metadata and controls