COSC 181 Foundations of Computer Programming Class 29 1 Next Test Monday April 20th 2 1 Fig 6 29 f ig06 29 cpp 2 Test ing the recurs ive fac to r ia l 3 inc lude iostream 4 us ing std cout 5 us ing std endl funct ion 6 7 inc lude iomanip 8 us ing std setw 9 10 uns igned long factorial unsigned long function prototype 11 12 int main 13 14 calculate the factorials of 0 through 10 15 for int counter 0 counter 10 counter 16 17 Outline fig06 2 9 cpp 1 of 2 cout setw 2 counter factorial counter endl 18 19 return 0 indicates successful termination 20 end main First call to factorial function 3 21 22 recurs ive def in i t io n of funct ion factor ia l 23 uns igned long factorial unsigned long number 24 25 if number 1 test for base case return 1 base cases 0 1 and 1 1 26 27 else recursion step return number factorial number 1 28 29 end funct ion factoria l 0 1 2 3 4 5 6 7 8 9 10 1 1 2 6 24 120 720 5040 40320 362880 3628800 Outline Base cases simply return 1 fig06 2 9 cpp 2 Recursive call to factorial function with a slightly smaller problem 4 of 2 In class Exercise 2 3 Write a program that asks the user for a number n The program then calls a recursive function that finds the sum of the first n integers It then prints out that sum What is the recursive relationship What is the base case 5 The two parts 1 Recursive Relationship 2 Base Case n IntSum n 1 n 1 the sum of the 1st integer is 1 There is an even better solution Any ideas n n 1 2 6 6 21 Recursion vs Iteration Both are based on a control statement Both involve repetition Both involve a termination test Iteration repetition structure Recursion selection structure Iteration explicitly uses repetition structure Recursion repeated function calls Iteration loop termination test Recursion base case 7 6 21 Recursion vs Iteration Cont Both gradually approach termination Iteration modifies counter until loop termination test fails Recursion produces progressively simpler versions of problem Both can occur infinitely Iteration if loop continuation condition never fails Recursion if recursion step does not simplify the problem 8 1 Fig 6 32 f ig06 32 cpp 2 3 inc lude iostream 4 5 6 us ing std cout us ing std endl 7 8 9 inc lude iomanip using std setw Test ing the it e ra t ive facto r ia l funct ion 10 uns igned longfactorial unsigned long function prototype 11 12 int main 13 14 calculate the factorials of 0 through 10 15 16 17 18 19 Outline fig06 3 2 cpp 1 for int counter 0 counter 10 counter cout setw 2 counter factorial counter endl return 0 20 end main 21 22 iterative function factorial 23 unsigned long factorial unsigned long number 24 25 unsigned long result 1 9 of 2 26 27 iterative declaration of function factorial 28 for unsigned long i number i 1 i 29 result i Iterative approach to finding a factorial 30 31 Outline return result 32 end funct ion factoria l 0 1 1 1 2 2 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880 10 3628800 fig06 3 2 cpp 2 10 of 2 6 21 Recursion vs Iteration Cont Negatives of recursion Overhead of repeated function calls Can be expensive in both processor time and memory space Each recursive call causes another copy of the function actually only the function s variables to be created Can consume considerable memory Iteration Normally occurs within a function Overhead of repeated function calls and extra memory assignment is omitted 11 Software Engineering Observation 6 18 Any problem that can be solved recursively can also be solved iteratively nonrecursively A recursive approach is normally chosen in preference to an iterative approach when the recursive approach more naturally mirrors the problem and results in a program that is easier to understand and debug Another reason to choose a recursive solution is that an iterative solution is not apparent 12 Performance Tip 6 9 Avoid using recursion in performance situations Recursive calls take time and consume additional memory 13 Common Programming Error 6 26 Accidentally having a nonrecursive function call itself either directly or indirectly through another function is a logic error 14 Location in Text Recursion Examples and Exercises Chapter 6 Section 6 19 Fig 6 29 Factorial function Section 6 19 Fig 6 30 Fibonacci function Exercise 6 7 Sum of two integers Exercise 6 40 Raising an integer to an integer power Exercise 6 42 Towers of Hanoi Exercise 6 44 Visualizing recursion Exercise 6 45 Greatest common divisor Exercise 6 50 Exercise 6 51 Mystery What does this program do exercise Fig 6 33 Summary of recursion examples and exercises in the text Part 1 of 3 15 Location in Text Recursion Examples and Exercises Chapter 7 Exercise 7 18 Mystery What does this program do exercise Exercise 7 21 Mystery What does this program do exercise Exercise 7 31 Selection sort Exercise 7 32 Determine whether a string is a palindrome Exercise 7 33 Linear search Exercise 7 34 Binary search Exercise 7 35 Eight Queens Exercise 7 36 Print an array Exercise 7 37 Print a string backward Exercise 7 38 Minimum value in an array Chapter 8 Exercise 8 24 Exercise 8 25 Exercise 8 26 Exercise 8 27 Quicksort Maze traversal Generating Mazes Randomly Mazes of Any Size Fig 6 33 Summary of recursion examples and exercises in the text Part 2 of 3 16