Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 161COSC 181 – Foundations of Computer ProgrammingClass 292Next TestMonday, April 20th31 // Fig. 6.29: f ig06_29.cpp2 / / Test ing the recurs ive factor ia l funct ion .3 #inc lude <iostream>4 us ing std::cout;5 us ing std::endl;67 #inc lude <iomanip>8 us ing std::setw;910 uns igned long factorial( unsigned long ); // function prototype1112 int main()13 {14 // calculate the factorials of 0 through 1015 for ( int counter = 0; counter <= 10; counter++ )16 cout << setw( 2 ) << counter << "! = " << factorial( counter ) 17 << endl;1819 return 0; // indicates successful termination20 } // end mainOutlinefig06_29.cpp (1 of 2)First call to factorial function42122 / / recurs ive def in it 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 26 return 1; // base cases: 0! = 1 and 1! = 127 else // recursion step 28 return number * factorial( number - 1 ); 29 } // end function factoria l 0! = 1 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 36288010! = 3628800Outlinefig06_29.cpp (2 of 2)Base cases simply return 1Recursive call to factorial function with a slightly smaller problem5In-class Exercise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.2. What is the recursive relationship?3. What is the base case?6The two parts 1. Recursive Relationship•n + IntSum(n-1)2. Base Case•n=1 (the sum of the 1st integer is 1)There is an even better solution •Any ideas?•(n(n+1)) / 276.21 Recursion vs. IterationBoth are based on a control statement•Iteration – repetition structure•Recursion – selection structureBoth involve repetition•Iteration – explicitly uses repetition structure•Recursion – repeated function callsBoth involve a termination test•Iteration – loop-termination test•Recursion – base case86.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 problem91 // Fig. 6.32: f ig06_32.cpp2 / / Test ing the it e rat ive factor ia l funct ion .3 #inc lude <iostream>4 us ing std::cout;5 us ing std::endl;67 #inc lude <iomanip>8 using std::setw;910 uns igned long factorial( unsigned long ); // function prototype1112 int main()13 {14 // calculate the factorials of 0 through 1015 for ( int counter = 0; counter <= 10; counter++ )16 cout << setw( 2 ) << counter << "! = " << factorial( counter ) 17 << endl;1819 return 0;20 } // end main2122 // iterative function factorial23 unsigned long factorial( unsigned long number )24 {25 unsigned long result = 1;Outlinefig06_32.cpp (1 of 2)102627 // iterative declaration of function factorial28 for ( unsigned long i = number; i >= 1; i-- ) 29 result *= i; 3031 return result;32 } // end function factoria l0! = 11! = 12! = 23! = 64! = 245! = 1206! = 7207! = 50408! = 403209! = 36288010! = 3628800 Outlinefig06_32.cpp (2 of 2)Iterative approach to finding a factorial116.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 omitted12Software 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.13Performance Tip 6.9 Avoid using recursion in performance situations. Recursive calls take time and consume additional memory.14Common Programming Error 6.26 Accidentally having a nonrecursive function call itself, either directly or indirectly (through another function), is a logic error.15Fig. 6.33 | Summary of recursion examples and exercises in the text. (Part 1 of 3) Location in Text Recursion Examples and ExercisesChapter 6Section 6.19, Fig. 6.29Factorial functionSection 6.19, Fig. 6.30Fibonacci functionExercise 6.7Sum of two integers Exercise 6.40Raising an integer to an integer power Exercise 6.42Towers of HanoiExercise 6.44Visualizing recursionExercise 6.45Greatest common divisor Exercise 6.50, Exercise 6.51Mystery “What does this program do?” exercise16Fig. 6.33 | Summary of recursion examples and exercises in the text. (Part 2 of 3) Location in Text Recursion Examples and ExercisesChapter 7Exercise 7.18 Mystery “What does this program do?” exerciseExercise 7.21 Mystery “What does this program do?” exerciseExercise 7.31Selection sortExercise 7.32Determine whether a string is a palindromeExercise 7.33Linear searchExercise 7.34Binary searchExercise 7.35Eight QueensExercise 7.36Print an arrayExercise 7.37Print a string backwardExercise 7.38Minimum value in an arrayChapter 8Exercise 8.24 QuicksortExercise 8.25 Maze traversalExercise 8.26 Generating Mazes RandomlyExercise 8.27 Mazes of Any