COSC 181 Foundations of Computer Programming Class 29 1 6 19 Recursion Recursive function A function that calls itself either directly or indirectly through another function Recursion Base case s The simplest case s which the function knows how to handle For all other cases the function typically divides the problem into two conceptual pieces A piece that the function knows how to do A piece that it does not know how to do Slightly simpler or smaller version of the original problem 2 6 19 Recursion Cont Recursion Cont Recursive call also called the recursion step The function launches calls a fresh copy of itself to work on the smaller problem Can result in many more recursive calls as the function keeps dividing each new problem into two conceptual pieces This sequence of smaller and smaller problems must eventually converge on the base case Otherwise the recursion will continue forever 3 6 19 Recursion Cont Factorial The factorial of a nonnegative integer n written n and pronounced n factorial is the product n n 1 n 2 1 Recursive definition of the factorial function n n n 1 Example 5 5 4 3 2 1 5 5 4 3 2 1 5 5 4 4 Fig 6 28 Recursive evaluation of 5 5 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 6 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 7 of 2 Common Programming Error 6 24 Either omitting the base case or writing the recursion step incorrectly so that it does not converge on the base case causes infinite recursion eventually exhausting memory This is analogous to the problem of an infinite loop in an iterative nonrecursive solution 8 6 20 Example Using Recursion Fibonacci Series The Fibonacci series 0 1 1 2 3 5 8 13 21 Begins with 0 and 1 Each subsequent Fibonacci number is the sum of the previous two Fibonacci numbers can be defined recursively as follows fibonacci 0 0 fibonacci 1 1 fibonacci n fibonacci n 1 fibonacci n 2 9 1 Fig 6 30 f ig06 30 cpp 2 3 inc lude iostream 4 us ing std cout 5 us ing std cin 6 us ing std endl Test ing the recurs ive f ibonacc i funct ion 7 8 uns igned long fibonacci unsigned long function prototype 9 10 int main 11 12 calculate the fibonacci values of 0 through 10 13 for int counter 0 counter 10 counter 14 15 Outline fig06 3 0 cpp 1 cout fibonacci counter fibonacci counter endl 16 17 display higher fibonacci values 18 cout fibonacci 20 fibonacci 20 endl 19 cout fibonacci 30 fibonacci 30 endl 20 cout fibonacci 35 fibonacci 35 endl 21 return 0 indicates successful termination 22 end main 23 10 of 2 24 25 26 27 28 29 30 31 recurs ive method f ibonacc i uns igned long fibonacci unsigned long number if number 0 number 1 base cases return number Base else recursion step return fibonacci number 1 fibonacci number 2 end funct ion f ibonacci fibonacci fibonacci fibonacci fibonacci fibonacci fibonacci fibonacci fibonacci fibonacci fibonacci fibonacci fibonacci fibonacci fibonacci 0 0 1 1 2 1 3 2 4 3 5 5 6 8 7 13 8 21 9 34 10 55 20 6765 30 832040 35 9227465 Outline cases fig06 3 Recursive calls to fibonacci function 0 cpp 2 of 2 11 Fig 6 31 Set of recursive calls to function fibonacci 12 Common Programming Error 6 25 Writing programs that depend on the order of evaluation of the operands of operators other than and the comma operator can lead to logic errors 13 Portability Tip 6 3 Programs that depend on the order of evaluation of the operands of operators other than and the comma operator can function differently on systems with different compilers 14 6 20 Example Using Recursion Fibonacci Series Cont Caution about recursive programs Each level of recursion in function fibonacci has a doubling effect on the number of function calls i e the number of recursive calls that are required to calculate the nth Fibonacci number is on the order of 2n 20th Fibonacci number would require on the order of 220 or about a million calls 30th Fibonacci number would require on the order of 230 or about a billion calls Exponential complexity Can humble even the world s most powerful computers 15 Performance Tip 6 8 Avoid Fibonacci style recursive programs that result in an exponential explosion of calls 16 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 17 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 18