《C++程序设计》（英文版） Chapter 15 Topics

Programming in c++ Recursion Dale/eems/Headington

1 Recursion

Programming in C++ Chapter 15 Topics Meaning of Recursion Base Case and General Case in Recursive Function definitions s Writing Recursive Functions with Simple Type Parameters s Writing Recursive Functions with Array Parameters wRiting Recursive Functions with Pointer Parameters Understanding How Recursion Works

2 Chapter 15 Topics ❖Meaning of Recursion ❖Base Case and General Case in Recursive Function Definitions ❖Writing Recursive Functions with Simple Type Parameters ❖Writing Recursive Functions with Array Parameters ❖Writing Recursive Functions with Pointer Parameters ❖Understanding How Recursion Works

Programming in C++ Recursive Function Call s a recursive call is a function call in which the called function is the same as the one making the call in other words, recursion occurs when a function calls itself g but we need to avoid making an infinite sequence of function calls (infinite recursion)

3 Recursive Function Call ❖a recursive call is a function call in which the called function is the same as the one making the call ❖in other words, recursion occurs when a function calls itself! ❖but we need to avoid making an infinite sequence of function calls (infinite recursion)

Programming in C++ Finding a Recursive Solution oa recursive solution to a problem must be written carefully & the idea is for each successive recursive call to bring you one step closer to a situation in which the problem can easily be solved o this easily solved situation is called the base case g each recursive algorithm must have at least one base case, as well as a general case (recursive case)

4 Finding a Recursive Solution ❖a recursive solution to a problem must be written carefully ❖the idea is for each successive recursive call to bring you one step closer to a situation in which the problem can easily be solved ❖this easily solved situation is called the base case ❖each recursive algorithm must have at least one base case, as well as a general case (recursive case)

Programming in C++ General format for Many Recursive Functions if (some easily-solved condition) //base case solution statement else ∥ genera/case recursive function call SOME EXAMPLES

5 General format for Many Recursive Functions if (some easily-solved condition) // base case solution statement else // general case recursive function call SOME EXAMPLES . .

Programming in C++ Writing a Recursive Function to Find the Sum of the Numbers from 1 to n DISCUSSION The function call Summation(4) should have value 10. because that is 1+2+3+4 For an easily-solved situation, the sum of the numbers from 1 to 1 is certainly just 1 So our base case could be along the lines of if(n==1) return 1

6 Writing a Recursive Function to Find the Sum of the Numbers from 1 to n DISCUSSION The function call Summation(4) should have value 10, because that is 1 + 2 + 3 + 4 . For an easily-solved situation, the sum of the numbers from 1 to 1 is certainly just 1. So our base case could be along the lines of if ( n == 1 ) return 1;

Programming in C++ Writing a Recursive Function to Find the Sum of the Numbers from 1 to n(Cont.) Now for the general case The sum of the numbers from 1 to n that is 1+2+.+n can be written as n+ the sum of the numbers from 1 to(n-1), that is,n+1+2+..+(n-1) or n Summation(n-1) And notice that the recursive call Summation(n-1) gets us"closer to the base case of Summation(1

7 Writing a Recursive Function to Find the Sum of the Numbers from 1 to n (Cont.) Now for the general case. . . The sum of the numbers from 1 to n, that is, 1 + 2 + . . . + n can be written as n + the sum of the numbers from 1 to (n - 1), that is, n + 1 + 2 + . . . + (n - 1) or, n + Summation(n - 1) And notice that the recursive call Summation(n - 1) gets us “closer” to the base case of Summation(1)

Programming in C++ Finding the Sum of the Numbers from 1 to n int Summation(/*in */int n) Computes the sum of the numbers from 1 to n by l adding n to the sum of the numbers from 1 to(n-1) ∥ Precondition n is assigned & n>0 ∥ Postcondition: l Function value =s sum of numbers from 1 to n f(n==1) ∥ base case return 1 else lgeneralcase return(n+ Summation(n-1)); 8

8 Finding the Sum of the Numbers from 1 to n int Summation ( /* in */ int n ) // Computes the sum of the numbers from 1 to n by // adding n to the sum of the numbers from 1 to (n-1) // Precondition: n is assigned && n > 0 // Postcondition: // Function value == sum of numbers from 1 to n { if ( n == 1) // base case return 1 ; else // general case return ( n + Summation ( n - 1 ) ) ; }

Programming in C++ Summation(4) Trace of Cal Returns 4+ Summation (3)=4+6=10 Call 1: n summation(4)4 Returns 3+ Summation(2)=3+3=6 Call 2. Summation (3) 3 Returns 2+ Summation(1) 2+1=3 ca|3: Summation(2)2 n==1 Returns Call 4. Summation(1) 9

9 Returns 4 + Summation(3) = 4 + 6 = 10 Call 1: Summation(4) Returns 3 + Summation(2) = 3 + 3 = 6 Call 2: Summation(3) Returns 2 + Summation(1) = 2 + 1 = 3 Call 3: Summation(2) n==1 Returns 1 Call 4: Summation(1) Summation(4) Trace of Call n 4 n 3 n 2 n 1

Programming in C++ Writing a Recursive Function to Find n Factorial DISCUSSION The function call Factorial(4) should have value 24 because that is 4*3*2*1 For a situation in which the answer is known. the value of 0! is 1 So our base case could be along the lines of if( number ==0) return 1 10

10 Writing a Recursive Function to Find n Factorial DISCUSSION The function call Factorial(4) should have value 24, because that is 4 * 3 * 2 * 1 . For a situation in which the answer is known, the value of 0! is 1. So our base case could be along the lines of if ( number == 0 ) return 1;