Original subtitles

1 1

(lively music) (keyboard clacking) 2

2

The next couple of algorithms we'll look at 3

3

can be written recursively 4

4

and they're often written recursively, 5

5

so let's take a brief timeout 6

6

and talk about recursion 7

7

to make sure we're all on the same page. 8

8

A method is a recursive method when it calls itself, 9

9

so we're gonna take a look at calculating the factorial 10

10

for a number. 11

11

As a reminder to calculate the factorial, 12

12

you start with the number 13

13

and then you multiply it by number minus one 14

14

and then you multiply the result by number minus two 15

15

and you multiply that result by number minus three et cetera 16

16

until you hit zero and then you stop. 17

17

So, three factorial would be three times two times one 18

18

which equals six. 19

19

100 factorial would 100 times 99 times 98 20

20

times 97, all the way down to times one 21

21

and the result of that is 9.332622 to the power of 157 22

22

which is a pretty large number. 23

23

Now, how about zero factorial? 24

24

Well, by definition that's equal to one. 25

25

So, zero factorial is one. 26

26

If you're wondering about negative numbers, 27

27

the factorials for negative numbers are undefined. 28

28

So, I have on the screen the factorial algorithm, 29

29

the steps for calculating the factorial. 30

30

We start out by saying if num is equal to zero, 31

31

so if we're taking num factorial, 32

32

if num is equal to zero, 33

33

then the factorial is one 34

34

and we stop, we have the result. 35

35

Otherwise we set the multiplier to one 36

36

and we set the factorial to one 37

37

and then while the multiplier is not equal to num, 38

38

we do steps five and six. 39

39

We multiply factorial by multiplier 40

40

and we assign the result to factorial 41

41

and then we add one to multiplier 42

42

and so, we'll say one times one, 43

43

add one to multiplier, so multiplier will become two, 44

44

so we'll have one times one times two 45

45

and then we'll assign two to factorial 46

46

and then we'll multiply that by three 47

47

and so, we'll assign six to factorial, 48

48

we'll multiply that by four, 49

49

assign 24 to factorial et cetera 50

50

and we keep going until multiplier 51

51

is equal to num at which point we stop. 52

52

So, that's another way of looking at it 53

53

instead of counting down and going three times two times one 54

54

for six factorial, 55

55

we can also say one times two times three. 56

56

It'll give us the same result. 57

57

So, in this algorithm, 58

58

we basically have a rinse-and-repeat step 59

59

which is step number four. 60

60

Step number four says that while the multiplier 61

61

is not equal to num, do steps five to six. 62

62

So, how would we code this? 63

63

Let's go out to IntelliJ 64

64

and we'll write the function 65

65

that calculates the factorial in an iterative way. 66

66

So, we'll use a for loop. 67

67

So, here I am in IntelliJ and I've created a project, 68

68

the package is academy.learnprogramming.recursion 69

69

and I'm going to write a method 70

70

to calculate the factorial in an iterative fashion 71

71

and that means we're not going to use recursion. 72

72

So, I'm gonna say public static, 73

73

static because we'll be calling it from the main method, 74

74

it's gonna return an integer, 75

75

the factorial and I'll call it iterativeFactorial 76

76

and of course we wanna pass in num. 77

77

So, the first thing we'll check is whether num equals zero 78

78

because if num equals zero, 79

79

we know that the result is one. 80

80

And so, we'll just return one. 81

81

If num doesn't equal zero, 82

82

we'll set a field called factorial to one 83

83

and then we'll say for int i equals one, 84

84

i less than or equal to num, i++ 85

85

factorial is assigned factorial times i. 86

86

And when we drop out of the loop, 87

87

we have the factorial, so we'll just return that. 88

88

So, what's happening here, 89

89

let's say we wanted to calculate three factorial 90

90

'cause we know that that's six, 91

91

so num is not equal to zero, 92

92

so we don't return, we'll set factorial to one, 93

93

i has to be less than or equal to three, 94

94

'cause we're passing in three, 95

95

so on the first iteration, the loop factorial 96

96

will be assigned factorial times one 97

97

and we start out with factorial being one, 98

98

so factorial will get one times one which is one, 99

99

i will become two, so factorial gets one times two 100

100

which is two and then i becomes three, 101

101

so factorial gets two times three which six 102

102

and then at this point, 103

103

i becomes four, it's no longer less than or equal to num, 104

104

so we drop out 105

105

and so, we return six. 106

106

So, that means three factorial is six. 107

107

And so, this an iterative implementation. 108

108

We're not using recursion, 109

109

the method does not call itself. 110

110

So, what about a recursive implementation? 111

111

Well, instead of using the loop, 112

112

we can have the method call itself 113

113

because think about it, 114

114

two factorial is one factorial times two, 115

115

three factorial is two factorial times three, 116

116

four factorial is three factorial times four. 117

117

I'm gonna write these out in a comment 118

118

so you can see what I mean, 119

119

so one factorial and usually we write factorial 120

120

using exclamation marks, 121

121

so one factorial equals zero factorial 122

122

which we know is one times one 123

123

which equals one, right? 124

124

Two factorial equals two times one 125

125

and this is actually two times one factorial 126

126

because we know that one factorial is one. 127

127

Three factorial equals three times two 128

128

times one and that's equivalent to three 129

129

times two factorial 130

130

because two factorial is two times one, 131

131

so that's three times two factorial. 132

132

Four factorial is equal to four 133

133

times three times two times one. 134

134

And that's equivalent to four 135

135

times three factorial because three factorial 136

136

is equal to three times two times one. 137

137

So, you can see the pattern now. 138

138

So, one factorial is I guess I should reverse that 139

139

for consistency, so one times zero factorial, 140

140

two factorial is two times one 141

141

which is two times one factorial, 142

142

three factorial is three times two times one 143

143

which is equivalent to three times two factorial, 144

144

four factorial is four times three 145

145

times two times one 146

146

which is equivalent to four times three factorial. 147

147

Five factorial would be five times four 148

148

times three times two times one 149

149

which is equivalent to five times four factorial. 150

150

And so, to calculate each factorial, 151

151

we can use a factorial. 152

152

Basically we multiply the num, the number 153

153

by n minus one factorial. 154

154

So, basically we're doing the following. 155

155

To get n factorial, that equals n minus one factorial 156

156

times n, right? 157

157

I'll do it like that 158

158

because that's how I wrote it above. 159

159

So, basically this is the formula we can use 160

160

to get the factorial of n, 161

161

it's equal to n times n minus one factorial. 162

162

And so, let's write a method 163

163

that uses this information. 164

164

So, we'll say public static int 165

165

and we'll call this one recursiveFactorial 166

166

and we'll pass in num as we did before 167

167

and we'll start out the same way. 168

168

If num equals zero, 169

169

then we return one. 170

170

We know that zero factorial is one. 171

171

Otherwise what are we gonna return? 172

172

Num times recursiveFactorial of num minus one. 173

173

Because we've just said that we can calculate 174

174

the factorial of n by multiplying n 175

175

by n minus one factorial 176

176

and so, here we're calling the same method, 177

177

we're calling the method itself 178

178

to get the value and here you can notice in the gutter, 179

179

IntelliJ has added this icon here 180

180

to tell us that we're making a recursive call. 181

181

But how does this actually work? 182

182

Let me move this up. 183

183

So, let's say we call recursiveFactorial 184

184

with a value of three. 185

185

Well, we're going to say does num equal zero? 186

186

No, it doesn't, so we'll come down 187

187

and we'll say okay, 188

188

we want to return three times recursiveFactorial of two. 189

189

Now, this doesn't return right away 190

190

because what's gonna happen 191

191

is we have to wait until we get the value 192

192

of recursiveFactorial num minus one, 193

193

and so, what will happen 194

194

is the call to recursiveFactorial 195

195

with a value of three is going to pushed 196

196

onto what's called the call stack 197

197

and then recursiveFactorial two 198

198

is going to be executed. 199

199

So, we haven't returned from recursiveFactorial three 200

200

'cause we have to wait for this result 201

201

and then we come into recursiveFactorial 202

202

with two into this call, 203

203

num isn't zero, so this time we're going to want 204

204

to return two times recursiveFactorial 205

205

of two minus one which is one, 206

206

so now the recursiveFactorial call 207

207

with the value two has to wait 208

208

and so, it's going to get pushed 209

209

onto the call stack 210

210

and recursiveFactorial one is going to be called. 211

211

So, basically at this point, we have two calls 212

212

to recursiveFactorial that are waiting 213

213

for a return value, 214

214

we call recursiveFactorial one, 215

215

one isn't zero, so we're gonna come down here 216

216

and return one times recursiveFactorial 217

217

of one minus one which is zero. 218

218

So, now the recursiveFactorial call with one 219

219

is gonna get pushed on the stack 220

220

because it's waiting and we call recursiveFactorial zero, 221

221

so we're gonna come in here, 222

222

ah, this time num is zero, 223

223

so we return one and this call is finished, 224

224

it doesn't get pushed onto the stack 225

225

but now the recursiveFactorial call with zero returns 226

226

and that's the call that recursiveFactorial 227

227

with the value one is waiting for. 228

228

So, now that call can resume 229

229

and it gets the return value of one 230

230

and so, it multiplies one by one 231

231

and it returns one 232

232

and now the call to recursiveFactorial two 233

233

can resume because it was waiting 234

234

for the return value of recursiveFactorial one. 235

235

And so, it multiplies two by one, 236

236

to get two, it returns two 237

237

and now the call to recursiveFactorial three can resume 238

238

because it was waiting for the return value 239

239

of recursiveFactorial two. 240

240

And so, it multiplies three by two, 241

241

it gets six, it returns and we have finished, 242

242

there's no more calls to recursiveFactorial 243

243

waiting on the call stack 244

244

and so, six gets returned 245

245

but you'll notice that the order 246

246

in which the recursive calls are made, 247

247

they return in the reverse order. 248

248

So, basically the situation that we have, 249

249

so we start out with calling recursiveFactorial three 250

250

and when it hits this line, 251

251

it calls recursiveFactorial two. 252

252

So, it can't return until it gets the value 253

253

of recursiveFactorial two and so, the call 254

254

to recursiveFactorial three 255

255

gets pushed onto the call stack. 256

256

Then recursiveFactorial two is called. 257

257

It can't return until it gets the result 258

258

of recursiveFactorial one. 259

259

And so, it gets pushed onto the call stack. 260

260

And then recursiveFactorial one 261

261

will get pushed onto the call stack 262

262

and recursiveFactorial zero 263

263

will actually return right away, 264

264

so when recursiveFactorial zero returns, 265

265

this gets popped off the call stack 266

266

and it continues executing 267

267

and it will return one 268

268

and when that returns, this gets popped up 269

269

off the call stack, it continues executing 270

270

and returns the value two 271

271

and finally this gets popped off the call stack 272

272

and it returns the value six. 273

273

That's how recursion works. 274

274

And it's important to see that when you enter 275

275

a recursive method, it might be a while 276

276

before it returns. 277

277

You can go down the rabbit hole 278

278

and you can go down, so when you see recursion 279

279

in the upcoming sort algorithms 280

280

that we're going to look at, 281

281

keep in mind that the call to a recursive method 282

282

may result in many more calls 283

283

before it returns, so it's important to understand 284

284

that a three-line recursive method 285

285

could result in hundreds of recursive calls. 286

286

The code might look simple 287

287

but it can lead to a tonne of processing. 288

288

And it's really important to understand 289

289

that none of the recursive calls return 290

290

until they receive the result 291

291

from the method that they invoked recursively, 292

292

so as we saw, recursiveFactorial three 293

293

invoked recursiveFactorial two, 294

294

so recursiveFactorial three is not going to return, 295

295

it can't return until recursiveFactorial two 296

296

has finished executing. 297

297

You'll notice here that the recursive calls 298

298

are ended when we pass num equals zero 299

299

because when we pass in num equals zero, 300

300

we don't make a recursive call, we just return one. 301

301

If we didn't have this condition, 302

302

we'd never end, we'd just keep making recursive call 303

303

after recursive call after recursive call. 304

304

So, in order for recursion to work properly, 305

305

you need some condition 306

306

that's going to end the recursion. 307

307

And that condition is known as the breaking condition 308

308

and it's also called the base case. 309

309

So, in the recursiveFactorial method, 310

310

this if num equals zero condition 311

311

is the base case or the breaking condition. 312

312

At that point, when num equals zero, 313

313

we say that the recursion starts to unwind, 314

314

so at that point it's gonna return a value 315

315

and the method that invoked it recursively 316

316

will now be able to continue executing 317

317

and then it will return a value 318

318

and the method that invoked it recursively 319

319

will be able to continue executing et cetera. 320

320

So, when you use recursion, 321

321

you need a breaking condition. 322

322

If you don't have one, 323

323

what will happen is the method 324

324

will keep calling itself recursively 325

325

and eventually you'll get a stack overflow exception 326

326

because the call stack only has a certain amount 327

327

of memory allocated to it. 328

328

And so, eventually you'll blow that memory. 329

329

So, let's run our recursive code. 330

330

Well, we'll run them both actually. 331

331

Let's System.out.print line 332

332

and we'll print out iterativeFactorial of three 333

333

and we'll do the same thing for recursiveFactorial three 334

334

and we should see six in both cases. 335

335

Let's run. 336

336

And sure enough, we get two sixes. 337

337

For fun, for fun and giggles, 338

338

let's remove the or just comment out this breaking condition 339

339

and you're gonna see what happens here, 340

340

it's not gonna be pretty. 341

341

And look at that. 342

342

We get all these recursive calls 343

343

until eventually we get a stack overflow error. 344

344

And so, we just keep, this method just keeps calling itself 345

345

and calling itself and calling itself 346

346

and there's nothing to stop it from doing that 347

347

and so, we have all these, 348

348

you're actually looking here at the call stack here, 349

349

so you're looking at all of the methods 350

350

that are on the call stack 351

351

and as you can see, it just keeps invoking itself 352

352

until we blow the call stack space. 353

353

I'll uncomment that now. 354

354

So, that's recursion. 355

355

Now, here's something interesting. 356

356

The iterative implementation usually runs faster 357

357

and it doesn't use as much memory 358

358

because there's overhead involved with pushing method calls 359

359

onto the call stack 360

360

and each stack frame uses some memory 361

361

but sometimes the iterative way isn't as intuitive 362

362

or if you write the algorithm 363

363

in an iterative way, it'll be like a 500-line method 364

364

or something like that, 365

365

so developers still use recursion 366

366

because it's often the most elegant 367

367

and more easier to understand solution. 368

368

Now, when we're dealing with the recursive method, 369

369

the call stack can also be referred 370

370

to as the recursion stack 371

371

and we saw that when we don't have a breaking condition, 372

372

we'll get a stack overflow exception. 373

373

It's possible to get that exception 374

374

even when you do have a breaking condition. 375

375

If you write a recursive method 376

376

and it invokes itself 1,000 times, 377

377

you're still possibly going 378

378

to get a stack overflow exception 379

379

because you're not hitting that breaking condition. 380

380

So, even if you have a breaking condition, 381

381

if you call the recursive method 382

382

with something that's going to cause the method 383

383

to invoke itself a million times, 384

384

you're gonna get a stack overflow error. 385

385

So, just keep that in mind. 386

386

Now, this is a way around this potential blowing 387

387

of the stack, it's called tail recursion 388

388

but we're not going to see that for two reasons. 389

389

First of all, none of the algorithms we look at, 390

390

none of the implementations use tail recursion 391

391

but the second and perhaps more important reason 392

392

for Java is that the Java compiler 393

393

doesn't use tail recursion, 394

394

so we can use that type of recursion in Java. 395

395

I'm just mentioning it to make you aware 396

396

that it exists and if you wanna read up on it yourself, 397

397

I've linked to a Dr. Dobbs article 398

398

in the Resources section, 399

399

so if you're interested in reading about tail recursion 400

400

in Java, you can go ahead and take a look at that article. 401

401

Anyway, I hope that this has refreshed your memory 402

402

about recursion and now that we're all on the same page, 403

403

we're gonna move on and look at a recursive sort algorithm 404

404

called merge sort. 405

405

I'll see you in the next video.