Programming in C++ Writing a Recursive Function to Find n Factorial (Cont Now for the general case The value of Factorial(n) can be written as n* the product of the numbers from (n-1)to 1 that is n*(n-1) or n* Factorial(n-1) And notice that the recursive call Factorial(n-1) gets us"closer" to the base case of Factorial(o)
11 Writing a Recursive Function to Find n Factorial (Cont.) Now for the general case . . . The value of Factorial(n) can be written as n * the product of the numbers from (n - 1) to 1, that is, n * (n - 1) * . . . * 1 or, n * Factorial(n - 1) And notice that the recursive call Factorial(n - 1) gets us “closer” to the base case of Factorial(0)
Programming in C++ Recursive Solution int Factorial( int number //Pre: number is assigned and number >=0 if( number == 0) ∥ base case return 1 else ∥ genera/case return number x Factorial( number-1) 12
12 Recursive Solution int Factorial ( int number ) // Pre: number is assigned and number >= 0. { if ( number == 0) // base case return 1 ; else // general case return number * Factorial ( number - 1 ) ; }
Programming in C++ Another Example Where Recursion Comes Naturally From mathematics, we know that 20=1and25=2*24 % In general x0= 1 and xn= x+xn-1 for integer x, and integer n>0. % Here we are defining xn recursively, in terms of xn-1 13
13 Another Example Where Recursion Comes Naturally ❖ From mathematics, we know that 2 0 = 1 and 25 = 2 * 24 ❖ In general, x 0 = 1 and xn = x * xn-1 for integer x, and integer n > 0. ❖ Here we are defining xn recursively, in terms of xn-1
Programming in C++ l/ Recursive definition of power function int Power( int x, int n) lI Pre: n >=0. x, n are not both zero l/ Post: Function value = x raised to the power n. if(n==0) return 1 ∥ base case else ∥ genera/case return(X* Power(X, n-1)) Of course, an alternative would have been to use looping instead of a recursive call in the function body 14
14 // Recursive definition of power function int Power ( int x, int n ) // Pre: n >= 0. x, n are not both zero // Post: Function value == x raised to the power n. { if ( n == 0 ) return 1; // base case else // general case return ( x * Power ( x , n-1 ) ) ; } Of course, an alternative would have been to use looping instead of a recursive call in the function body
Programming in C++ Extending the Definition what is the value of 2-3? again from mathematics, we know that it is -3 3 1/8 o in general, x =1/x-n for non-zero x, and integer n<0 s here we are again defining xn recursively, in terms of x-n when n< o 15
15 Extending the Definition ❖ what is the value of 2 -3 ? ❖ again from mathematics, we know that it is 2 -3 = 1 / 23 = 1 / 8 ❖ in general, x n = 1/ x -n for non-zero x, and integer n < 0 ❖ here we are again defining xn recursively, in terms of x-n when n < 0