Recursion

Chapter 4: Recursion • Subprogram implementation • Recursion • Designing recursive algorithms • Recursion removal • Backtracking

1

Subprogram implementation function FOO(X: real; Y: integer): real; var A: array [1..10] of real; N: integer; begin … N := Y + 1; X := A[N] ∗ 2; … end;

2

Subprogram implementation • Code segment (static part) • Activation record (dynamic part): – Parameters – Function results – Local variables

3

Subprogram implementation Prologue Statement executabl e codes

Epilogue

Code segment

FOO X Y A

Return point and system data

N

Activation record 4

Subprogram implementation Code segment

1st call Activation record 1

2nd call Activation record 2

N-th call Activation record N

5

Recursion An object contains itself

6

Recursion • A definition contains itself: – Sibling(X, Y): X and Y have the same parents – Cousin(X, Y): X’s and Y’s parents are siblings OR cousins

7

Recursion • Recursive algorithm is a repetitive process that contains (call) itself: – Direct: A → A – Indirect: A → B → A

8

Recursion • Does human thinking involve recursion?

9

Factorial Iterative algorithm 1 0 Factorial(n) =

if n =

n × (n − 1) × (n − 2) ×...× 3 × 2 × 1 if n

>0 Recursive algorithm 0 Factorial(n) = 0

1

if n =

n × (Factorial(n − 1))

if n >

10

Iterative Solution Algorithm iterativeFactorial (val n ) Calculates the factorial of a number using a loop Pre

n is the number to be raised factorially

Return n! is returned 1 i=1 2 factN = 1 3 loop (i <= n) 1 factN = factN + 1 2 i=i+1 4 return factN End iterativeFactorial 11

Recursive Solution Algorithm recursiveFactorial (val n ) Calculates the factorial of a number using recursion Pre

n is the number to be raised factorially

Return n! is returned 1 if (n = 0) 1 factN = 1 2 else 1 factN = n × recursiveFactorial(n − 1) 3 return factN End recursiveFactorial 12

Recursive Solution Factorial(3) = 3 × Factorial(2)

Factorial(3) = 3

×2=6

Factorial(2) = 2

× Factorial(1)

Factorial(2) = 2

×1=2

Factorial(1) = 1

× Factorial(0)

Factorial(1) = 1

×1=1

Factorial(0) = 1 13

Recursive Solution code segment

Algorithm recursiveFactorial (val n ) 1 if (n = 0) 1 factN = 1 2 else 1 factN = n × recursiveFactorial(n − 3 return factN

recursiveFactorial()

return addres s 1)

activation record return address

End recursiveFactorial n factN

14

Recursive Solution 0

n

3

1

1

2

2

2

3

3

3

factN

stack s

15

Recursive Solution 0 1

n

1

1 1

2

2

2 2

3

3

3

factN

stack s

3 6

16

Designing Recursive Algorithms Recursive algorithm = recursive case + stopping case n × factorial(n − 1)

factorial(0)

17

Designing Recursive Algorithms

• Every recursive call must solve a part of the problem or reduce the size of the problem.

18

Designing Recursive Algorithms

• Determine the recursive case • Determine the stopping case

• Combine the recursive and stopping cases

19

Designing Recursive Algorithms

• Is the algorithm or data structures naturally suited to recursion? • Is the recursive solution shorter and more understandable? • Does the recursive solution run in acceptable time and space limits?

20

Print List in Reverse

6

10

20 6

14

14

20

10

21

Print List in Reverse

6

10

20 6

14

14

20

10

22

Print List in Reverse Algorithm printReverse (val list <pointer>) Prints singly linked list in reverse Pre list has been built Post list printed in reverse 1 if (null list)

stopping case

1 return 2 printReverse (list −> next)

recursive case

3 print (list −> data) End printReverse

23

Print List in Reverse • Is the algorithm or data structures naturally suited to recursion? • Is the recursive solution shorter and more understandable? • Does the recursive solution run in acceptable time and space limits?

24

Fibonacci Numbers 0

1

1

2 3

5

8

13

21

34

• Recursive case: Fib(n) = Fib(n − 1) + Fib(n − 2) • Stopping case: Fib(0) = 0

Fib(1) = 1

25

Fibonacci Numbers Fib(n ) Fib(n1) Fib(n2) Fib(n3)

Fib(n2) Fib(n3)

Fib(n3)

Fib(n4)

Fib(n4) 26

Fibonacci Numbers Fib(4 5 ) Fib(3) 3

Fib(2) 2

Fib(1) 1

Fib(1) 1

Fib(2) 2

Fib(1) 1

Fib(0) 0

Fib(0) 0 27

Fibonacci Numbers Algorithm fib (val num ) Calculates the nth Fibonacci number Pre

num is the ordinal of the Fibonacci number

Post

returns the nth Fibonacci number

1 if (num = 0 OR num = 1)

stopping case

1 return num 2 return (fib(n - 1) + fib(n - 2)) recursive case End fib

28

Fibonacci Numbers No

Calls

Time

No

Calls

Time

1

1

< 1 sec.

11

287

< 1 sec.

2

3

< 1 sec.

12

465

< 1 sec.

3

5

< 1 sec.

13

753

< 1 sec.

4

9

< 1 sec.

14

1,219

< 1 sec.

5

15

< 1 sec.

15

1,973

< 1 sec.

6

25

< 1 sec.

20

21,891

< 1 sec.

7

41

< 1 sec.

25

242,785

1 sec.

8

67

< 1 sec.

30

2,692,573

7 sec.

9

109

< 1 sec.

35

29,860,703

1 min.

10

177

< 1 sec.

40

331,160,28 1

< 13 min.

29

The Towers of Ha Noi Move disks from Source to Destination using Auxiliary: 1. Only one disk could be moved at a time. 2. A larger disk must never be stacked above a smaller one. 3. Only one auxiliary needle could be used for the intermediate storage of disks.

Source

Auxiliar y

Destinati on

30

The Towers of Ha Noi

Source

Auxiliary Destination

Source

Auxiliary Destination

Source

Auxiliary Destination

Source

Auxiliary Destination

31

The Towers of Ha Noi move(n, A, C, B)

A

B

move(n-1, A, B, C)

A

C

A

B

move(1, A, C, B)

B

C

C

move(n-1, B, C, A)

A

B

C 32

The Towers of Ha Noi move(3, A, C, B)

move(1, A, C, B)

A→ C

move(2, A, B, C) move(1, A, B, move(1, A, C, C) A→ B)

A→ C

B

move(1, B, C, move(1, B, A, A) B→ C)

move(1, C, B, A)

C→ B

A

move(2, B, C, A)

B→ A

B

C

move(2, C, B, A)

C→ B

C 33

The Towers of Ha Noi • Complexity: T(n) = 2×T(n – 1) + 1 ⇒ T(n) = O(2n)

34

The Towers Algorithm Algorithm towers (val disks , val source , val dest , val auxiliary , ref step ) Move disks from source to destination Pre Post

disks is the number of disks to be moved steps for moves printed

35

The Towers Algorithm 1 print("Towers: ", disks, source, dest, auxiliary) 2 if (disks = 1) 1 print ("Step ", step, "Move from", source, "to", dest) 2 step = step + 1 3 else 1 towers (disks - 1, source, auxiliary, dest, step) 2 towers (1, source, dest, auxiliary, step) 3 towers (disks - 1, auxiliary, dest, source, step) 4 return End towers

36

Recursion Removal • Recursion can be removed using stacks and iteration.

37

Recursion Removal Algorithm P (val n ) 1 if (n = 0) 1 print ("Stop") 2 else 1 Q(n) 2 P(n - 1) 3 R(n) End P

38

Recursion Removal Algorithm P (val n ) ) 1 if (n = 0) 1 print ("Stop") 2 else 1 Q(n) 2 P(n - 1) 3 R(n) End P (s))

Algorithm P (val n 1 createStack (s) 2 loop (n > 0) 1 Q(n) 2 push(s, n) 3 n=n-1 3 print ("Stop") 4 loop (not emptyStack 1 popStack(s, n) 2 R(n) 4 End P

39

Tail Recursion • Recursive call is the last statement.

40

Tail Recursion Algorithm P (val n ) 1 if (n = 0) 1 print("Stop") 2 else 1 Q(n) 2 P(n - 1) End P

41

Tail Recursion Algorithm P (val n ) 1 if (n = 0) 1 print("Stop") 2 else 1 Q(n) 2 P(n - 1) End P

Algorithm P (val n ) 1 loop (n > 0) 1 Q(n) 2 n=n-1 2 print("Stop") End P

42

Backtracking • A process to go back to previous steps to try unexplored alternatives.

43

Goal Seeking

6 4

start

1

2

7

5

3

8 9

12

13

10 14

17

15

11

goal

16

18

44

Eight Queens Problem Place eight queens on the chess board in such a way that no queen can capture another.

Q Q

Q Q Q 45

Eight Queens Problem 1 1

2

3

4

Q

1 1

2

3

4

Q

1 Q

1 4 Q

2

3

1 1 Q

2

2

3

3

3

3

4

4

4

4

1 1

2 Q

3

4

1 1

2

3

2

4

Q

1 Q

2

2

3

3

3

4

4

4

1 4

2

Q

Q Q

1

2

3

4

4

Q Q

2 3

4

Q

1 Q

2

3

2

3

Q

2

Q Q 46

Eight Queens Problem Algorithm putQueen (ref board <array>, val r ) Place remaining queens safely from a row of a chess board Pre

board is 8×8 array representing a chess board r is the row to place queens onwards

Post all the remaining queens are safely placed on the board; or backtracking to the previous rows is required

47

Eight Queens Problem 1 for every column c on the same row r 1 if (column c is safe) 1 place the next queen in column c 2 if (r < 8) 1 putQueen (board, r + 1) 3 else 1 output successful placement 4 remove the queen from column c 2 return End putQueen

48

Eight Queens Problem 1 for every column c on the same row r 1 if (column c is safe) 1 place the next queen in column c board[r][c] = 1 2 if (r < 8) 1 putQueen (board, r + 1) 3 else 1 output successful placement 4 remove the queen from column c 2 return End putQueen

49

Eight Queens Problem 1 for every column c on the same row r 1 if (column c is safe) 1 place the next queen in column c 2 if (r < 8) 1 putQueen (board, r + 1) 3 else 1 output successful placement 4 remove the queen from column c 2 return End putQueen

50

Eight Queens Problem 1 for every column c on the same row r 1 if (column c is safe) 1 place the next queen in column c board[r][c] = 1 2 if (r < 8) 1 putQueen (board, r + 1) 3 else

usedCol[c] = 1 usedDR[r+c] = 1 usedDL[r−c] = 1

1 output successful placement 4 remove the queen from column c 2 return End putQueen

51

Eight Queens Problem 1 for every column c on the same row r 1 if (column c is safe)

usedCol[c] is 0

1 place the next queen in column c usedDR[r+c] is 0 usedDL[r−c] is 0 2 if (r < 8) 1 putQueen (board, r + 1) 3 else 1 output successful placement 4 remove the queen from column c 2 return End putQueen

52

Eight Queens Problem 1 for every column c on the same row r 1 if (column c is safe) 1 place the next queen in column c 2 if (r < 8) 1 putQueen (board, r + 1) 3 else 1 output successful placement 4 remove the queen from column c board[r][c] = 0 usedCol[c] = 0 2 return usedDR[r+c] = 0 End putQueen usedDL[r−c] = 0 53

Eight Queens Problem 1 for every column c on the same row r 1 if (column c is safe) 1 place the next queen in column c 2 if (r < 8) 1 putQueen (board, r + 1) 3 else 1 output successful placement 4 remove the queen from column c

Top-down + Stepwise Refinement

2 return End putQueen

54