# Functions ###### tags: `PD` --- ## 6.1 Intro **Divide and Conquer** * construct a large program from **small, simple piecies, or components** to develop and maintain it. 其他內容後面都有 --- ## 6.2 Program Components in C++ * purpose $\rightarrow$ modularize a program * motivations * divide-and-conquer approach * software reuse * avoid repeating code * make debug and maintain easier * :::spoiler eg. C++ Standard Library * common mathematical calculations * string manipulations * character manipulations * input/output * error checking * etc. ::: * A boss (similar to the calling function) asks a worker (similar to the called function) to perform a task and report back (i.e., return) the results after completing the task.  --- ## 6.3 Math Library Functions * global functions * the function prototypes for global functions are placed in headers, so that the global functions can be reused in any program that includes the header and that can link to the function’s object code * eg. all functions in the `<cmath>` header are global functions *   --- ## 6.4 Function Definitions with Multiple Parameters 直接進入範例講解囉 Section1. Definition of class GradeBook that finds the maximum of three grades ```cpp= // Member functions are defined in GradeBook.cpp #include <string> //using C++ string class using namespace std; class GradeBook { public: GradeBook( string ); // constructor initializes course name void setCourseName( string ); // function to set the course name string getCourseName(); // function to retrieve the course name void displayMessage(); // display a welcome message void inputGrades(); // input three grades from user void displayGradeReport(); // display a report based on the grades int maximum( int, int, int ); // determine max of 3 values private: string courseName; // course name for this GradeBook int maximumGrade;// maximum of three grades }; ``` Seciton2. GradeBook class defines function maximum ```cpp= #include <iostream> using namespace std; #include "GradeBook.h" // include definition of class GradeBook // constructor initializes courseName with string supplied as argument; // initializes maximumGrade to 0 GradeBook::GradeBook( string name ) { setCourseName( name ); // validate and store courseName maximumGrade = 0; // this value will be replaced by the maximum grade } // function to set the course name; limits name to 25 or fewer characters void GradeBook::setCourseName( string name ) { if ( name.length() <= 25 ) // if name has 25 or fewer characters courseName = name; // store the course name in the object else // if name is longer than 25 characters { // set courseName to first 25 characters of parameter name courseName = name.substr( 0, 25 ); // select first 25 characters cout << "Name \"" << name << "\" exceeds maximum length (25).\n"<< "Limiting courseName to first 25 characters.\n" << endl; } // end if...else } // end function setCourseName // function to retrieve the course name string GradeBook::getCourseName() { return courseName; } // end function getCourseName // display a welcome message to the GradeBook user void GradeBook::displayMessage() { // this statement calls getCourseName to get the // name of the course this GradeBook represents cout << "Welcome to the grade book for\n" << getCourseName() << "!\n"<< endl; } // end function displayMessage // input three grades from user; determine maximum void GradeBook::inputGrades() { int grade1; // first grade entered by user int grade2; // second grade entered by user int grade3; // third grade entered by user cout << "Enter three integer grades: "; cin >> grade1 >> grade2 >> grade3; // store maximum in member maximumGrade maximumGrade = maximum( grade1, grade2, grade3 ); } // end function inputGrades // returns the maximum of its three integer parameters int GradeBook::maximum( int x, int y, int z ) { int maximumValue = x; // assume x is the largest to start //determine whether y is greater than maximumValue if ( y > maximumValue ) maximumValue = y; // make y the new maximumValue //determine whether z is greater than maximumValue if ( z > maximumValue ) maximumValue = z; // make z the new maximumValue return maximumValue; } // end function maximum // display a report based on the grades entered by user void GradeBook::displayGradeReport() { // output maximum of grades entered cout << "Maximum of grades entered: " << maximumGrade << endl; } // end function displayGradeReport ``` Section3. Demonstrating function maximum ```cpp= // Create GradeBook object, input grades and display grade report #include "GradeBook.h" // include definition of class GradeBook int main() { // create GradeBook object GradeBook myGradeBook( "CS101 C++ Programming" ); myGradeBook.displayMessage(); // display welcome message myGradeBook.inputGrades(); // read grades from user myGradeBook.displayGradeReport(); // display report based on grades 13 }//endmain ``` Section4. Output Result ``` Welcome to the grade book for CS101 C++ Programming! Enter three integer grades: 86 67 75 Maximum of grades entered: 86 ``` ``` Welcome to the grade book for CS101 C++ Programming! Enter three integer grades: 67 86 75 Maximum of grades entered: 86 ``` ``` Welcome to the grade book for CS101 C++ Programming! Enter three integer grades: 67 75 86 Maximum of grades entered: 86 ``` --- ## 6.5 Function Prototypes and Argument Coercion A function Prototype = A function declaration 函數宣告 1. function name 2. return data type 3. recieve parameter numbers 4. parameter data type * Function Signature include function name, parameter numbers, parameter types * Argument Promotion Rules C++’s promotion rules 舉幾個例子看一下～ * convert **int $\rightarrow$ double** ($\checkmark$) * convert **double $\rightarrow$ int** ($\times$, decimals will be truncated) * convert **large integer types $\rightarrow$ small integer types** ($\times$, may be modified!) * convert **signed to unsigned** ($\times$, may be modified!) * convert **unsigned to signed** ($\times$, may be modified!) * convert **mixed-type expressions** （expressions containing values of two or more data types） 電腦會選擇 the “highest” type 以下圖片排序是 from “highest type” to “lowest type.”  --- ## 6.6 C++ Standard Library Headers C++的參考列表，有興趣自己看看～     --- ## 6.7 Case Study: Random Number Generation `i = rand();` The function rand generates an unsigned integer between 0 and RAND_MAX (a symbolic constant defined in the <cstdlib> header). If rand truly produces integers at random, every number between 0 and RAND_MAX has an equal chance (or probability) of being chosen each time rand is called. ### Rolling a Six-Sided Die The function prototype for the rand function is in <cstdlib>. To produce integers in the range 0 to 5, we use the modulus operator (%) with rand as follows: `rand() % 6` This is called **scaling**. The number 6 is called the **scaling factor**. We then shift the range of numbers produced by adding 1 to our previous result.   ### Rolling a Six-Sided Die 6,000,000 Times To show that the numbers produced by `rand` occur with approximately equal likelihood, Fig. 6.9 simulates 6,000,000 rolls of a die. Each integer in the range 1 to 6 should appear approximately 1,000,000 times.   ### Using Function `srand` The program uses the data type **unsigned**, which is short for **unsigned int**. * An **int** is stored in at least two bytes of memory (typically four bytes on 32-bit systems and as much as eight bytes on 64-bit systems) and can have positive and negative values. * A variable of type **unsigned int** is also stored in at least two bytes of memory.A **two-byte unsigned int** can have only nonnegative values in the range 0–65535. A **four-byte unsigned int** can have only nonnegative values in the range 0– 4294967295. Function `srand` takes an **unsigned int** value as an argument. The function prototype for the srand function is in header`<cstdlib>`.   To randomize without having to enter a seed each time, we may use a statement like `srand( time( 0 ) );` This causes the computer to read its clock to obtain the value for the seed. * Function `time` (with the argument 0 as written in the preceding statement) typically returns the current time as the number of seconds since January 1, 1970, at midnight Greenwich Mean Time (GMT). This value is converted to an unsigned integer and used as the seed to the random number generator. The function prototype for time is in <ctime>. ### Generalized Scaling and Shifting of Random Numbers `face = 1 + rand() % 6;` We can generalize this result as `number = shiftingValue + rand() % scalingFactor;` --- ## 6.8 Case Study: Game of Chance; Introducing enum One of the most popular games of chance is a dice game known as “craps,” the rules are as follows. *A player rolls two dice. Each die has six faces. These faces contain 1, 2, 3, 4, 5 and 6 spots. After the dice have come to rest, the sum of the spots on the two upward faces is calculated. If the sum is 7 or 11 on the first roll, the player wins. If the sum is 2, 3 or 12 on the first roll (called “craps”), the player loses (i.e., the “house” wins). If the sum is 4, 5, 6, 8, 9 or 10 on the first roll, then that sum becomes the player’s “point.” To win, you must continue rolling the dice until you “make your point.” The player loses by rolling a 7 before making the point.*    Line 13 declares a user-defined type called an **enumeration**. * An **enumeration**, introduced by the keyword **`enum`** and followed by a type name (in this case, Status), is a set of integer constants represented by identifiers. * The values of these enumeration constants start at 0, unless specified otherwise, and increment by 1. In the preceding enumeration, the constant CONTINUE has the value 0, WON has the value 1 and LOST has the value 2. * The identifiers in an enum must be unique, but separate enumeration constants can have the same integer value. * Use only **uppercase letters** in enumeration constant names. --- ## 6.9 Storage Classes C++ provides five storage-class specifiers: **auto**, **register**, **extern**, **mutable** and **static**. ### Storage Class, Scope and Linkage * An identifier’s *scope* is where the identifier can be referenced in a program. * An identifier’s linkage determines whether it’s known only in the source file where it’s declared or across multiple files that are compiled, then linked together. An identifier’s storage-class specifier helps determine its storage class and linkage. ### Storage Class Categories * The storage-class specifiers can be split into two storage classes: **automatic** storage class and **static** storage class * Keywords `auto` and `register` are used to declare variables of the automatic storage class. * Such variables are created when program execution enters the block in which they’re defined, they exist while the block is active and they’re destroyed when the program exits the block. ### Local Variables * Only local variables of a function can be of automatic storage class. * A function’s local variables and parameters normally are of automatic storage class. * The storage class specifier `auto` explicitly declares variables of automatic storage class. * Local variables are of automatic storage class by default, so keyword auto rarely is used. * Automatic storage is a means of conserving memory, because automatic storage class variables exist in memory only when the block in which they’re defined is executing. ### Register Variables * Data in the machine-language version of a program is normally loaded into registers for calculations and other processing. * The storage-class specifier register can be placed before an automatic variable declaration to suggest that the compiler maintain the variable in one of the computer’s high-speed hard- ware registers rather than in memory. * The compiler might ignore register declarations. eg. there might not be a sufficient number of registers available. * The register keyword can be used only with local variables and function parameters.  * Often, register is unnecessary. Optimizing compilers can recognize frequently used vari- ables and may place them in registers without needing a register declaration. ### Static Storage Class * Keywords `extern` and `static` declare identifiers for variables of the static storage class and for functions. * Static-storage-class variables exist in memory from the point at which the program begins execution and last for the duration of the program. * Such a variable is initialized once when its declaration is encountered. For functions, the name of the function exists when the program begins execution, just as for all other functions. * However, even though the variables and the function names exist from the start of program execution, this does not mean that these identifiers can be used throughout the program. ### Identifiers with Static Storage Class * There are two types of identifiers with static storage class—external identifiers (such as global variables) and local variables declared with the storage-class specifier `static`. * #### Global variables : * created by placing variable declarations outside any class or function definition. * Global variables retain their values throughout the execution of the program. * Global variables and global functions can be referenced by any function that follows their declarations or definitions in the source file. * #### Local variables : * declared `static` are still known only in the function in which they’re declared, but, unlike automatic variables, static local variables retain their values when the function returns to its caller. The next time the function is called, the static local variables contain the values they had when the function last completed execution. * The following statement declares local variable count to be static and to be initialized to 1 :  * All numeric variables of the static storage class are initialized to zero by default, but it’s nevertheless a good practice to explicitly initialize all variables. --- ## 6.10 Scope Rules ### Function scope ### Global namespace scope * An identifier declared outside any function or class has global namespace scope. * Such an identifier is “known” in all functions from the point at which it’s declared until the end of the file. Global variables, function definitions and function prototypes placed outside a function all have global namespace scope. ### Local scope * Identifiers declared inside a block have local scope. * Local scope begins at the identifier’s declaration and ends at the terminating right brace (}) of the block in which the identifier is declared. * Local variables have local scope, as do function parameters, which are also local variables of the function. * Any block can contain variable declarations. When blocks are nested and an identifier in an outer block has the same name as an identifier in an inner block, the identifier in the outer block is “hidden” until the inner block terminates. The inner block “sees” the value of its own local identifier and not the value of the identically named identifier in the enclosing block. * Local variables declared static still have local scope, even though they exist from the time the program begins execution. Storage duration does not affect the scope of an identifier. ### Function-prototype scope * The only identifiers with function prototype scope are those used in the parameter list of a function prototype. * Function prototypes do not require names in the parameter list — only types are required. Names appearing in the parameter list of a function prototype are ignored by the compiler. * Identifiers used in a function prototype can be reused elsewhere in the program without ambiguity. In a single prototype, a particular identifier can be used only once.    --- ## 6.11 Function Call Stack and Activation Records * Think of a stack as analogous to a pile of dishes. When a dish is placed on the pile, it’s normally placed at the top (referred to as pushing the dish onto the stack). Similarly, when a dish is removed from the pile, it’s normally removed from the top (referred to as popping the dish off the stack). Stacks are known as last-in, first-out (LIFO) data structures—the last item pushed (inserted) on the stack is the first item popped (removed) from the stack. * The **function call stack** is the perfect data structure for handling this information. Each time a function calls another function, an entry is pushed onto the stack. This entry, called a stack frame or an activation record, contains the return address that the called function needs in order to return to the calling function. * Most functions have **automatic variables**—parameters and any local variables the function declares. Automatic variables need to exist while a function is executing. They need to remain active if the function makes calls to other functions. But when a called function returns to its caller, the called function’s automatic variables need to “go away.” * The called function’s stack frame is a perfect place to reserve the memory for the called function’s automatic variables. That stack frame exists as long as the called function is active. When that function returns—and no longer needs its local automatic variables—its stack frame is popped from the stack, and those local automatic variables are no longer known to the program. * Of course, the amount of memory in a computer is finite, so only a certain amount of memory can be used to store activation records on the function call stack. If more func- tion calls occur than can have their activation records stored on the function call stack, an error known as stack overflow occurs. ### Function Call Stack in Action Now let’s consider how the call stack supports the operation of a square function called by main (lines 9–14 of Fig. 6.13).   First the operating system calls main—this pushes an activation record onto the stack (shown in Fig. 6.14).  Function main—before returning to the operating system—now calls function square in line 13 of Fig. 6.13. This causes a stack frame for square (lines 17–20) to be pushed onto the function call stack (Fig. 6.15). This stack frame contains the return address that square needs to return to main (i.e., R2) and the memory for square’s auto- matic variable (i.e., x).   After square calculates the square of its argument, it needs to return to main—and no longer needs the memory for its automatic variable x. So the stack is popped—giving square the return location in main (i.e., R2) and losing square’s automatic variable. Figure 6.16 shows the function call stack after square’s activation record has been popped.  Function main now displays the result of calling square (line 13). Reaching the closing right brace of main causes its activation record to be popped from the stack, gives main the address it needs to return to the operating system (i.e., R1 in Fig. 6.14) and causes the memory for main’s automatic variable (i.e., a) to become unavailable. --- ## 6.12 Functions with Empty Parameter Lists In C++, an empty parameter list is specified by writing either void or nothing at all in parentheses. The prototype  specifies that function print does not take arguments and does not return a value.  --- ## 6.13 Inline Functions * Implementing a program as a set of functions is good from a software engineering standpoint, but function calls involve execution-time overhead. C++ provides **inline functions** to help reduce function call overhead—especially for small functions. * Placing the qualifier inline before a function’s return type in the function definition “advises” the compiler to generate a copy of the function’s body code in place (when appropriate) to avoid a function call. * Any change to an inline function requires all clients of the function to be recompiled.   --- ## 6.14 References and Reference Parameters * Two ways to pass arguments to functions in many programming languages are pass-by-value and pass-by-reference. * When an argument is passed by value, a copy of the argument’s value is made and passed (on the function call stack) to the called function. Changes to the copy do not affect the original variable’s value in the caller. This prevents the accidental side effects that so greatly hinder the development of correct and reliable software systems. * One disadvantage of pass-by-value is that, if a large data item is being passed, copying that data can take **a considerable amount of execution time and memory space**. ## Reference Parameters * With **pass-by-reference**, the caller gives the called function the ability to **access the caller’s data directly**, and to modify that data. * Pass-by-reference is good for performance reasons, because it can eliminate the pass-by-value overhead of copying large amounts of data. * To indicate that a function parameter is passed by reference, simply follow the parameter’s type in the function prototype by an **ampersand (&)** ; use the same convention when listing the parameter’s type in the function header. * For example, the following declaration in a function header  when read from right to left is pronounced “count is a reference to an int.” * In the function call, simply mention the variable by name to pass it by reference. Then, mentioning the variable by its parameter name in the body of the called function actually refers to the original variable in the calling function, and the original variable can be modified directly by the called function. ## Passing Arguments by Value and by Reference * Figure 6.19 compares pass-by-value and pass-by-reference with reference parameters. The “styles” of the arguments in the calls to function `squareByValue` and function `squareByReference` are identical—both variables are simply mentioned by name in the function calls.   ## References as Aliases within a Function * References can also be used as aliases for other variables within a function (although they typically are used with functions as shown in Fig. 6.19). For example, the code  * increments variable count by using its alias cRef. Reference variables must be initialized in their declarations (see Fig. 6.20 and Fig. 6.21) and cannot be reassigned as aliases to other variables. Once a reference is declared as an alias for another variable, all operations sup- posedly performed on the alias (i.e., the reference) are actually performed on the original variable. The alias is simply another name for the original variable.     ## Returning a Reference from a Function * Functions can return references, but this can be dangerous. * When returning a reference to a variable declared in the called function, unless that variable is declared static, the reference refers to an automatic variable that’s discarded when the function terminates. Such a variable is said to be “undefined,” and the program’s behavior is unpredictable. References to undefined variables are called **dangling references**. ## Error Messages for Uninitialized References * The C++ standard does not specify the error messages that compilers use to indicate par- ticular errors. For this reason, Fig. 6.21 shows the error messages produced by the Micro- soft Visual C++ 2008 compiler and GNU C++ compiler when a reference is not initialized. --- ## 6.15 Default Arguments * When a program omits an argument for a parameter with a default argument in a function call, the compiler rewrites the function call and inserts the default value of that argument. * Default arguments must be the rightmost (trailing) arguments in a function’s parameter list. When calling a function with two or more default arguments, if an omitted argument is not the rightmost argument in the argument list, then all arguments to the right of that argument also must be omitted. * Default arguments must be specified with the first occurrence of the function name—typically, in the function prototype. If the func- tion prototype is omitted because the function definition also serves as the prototype, then the default arguments should be specified in the function header. * Default values can be any expression, including constants, global variables or function calls. Default arguments also can be used with inline functions. * Figure 6.22 demonstrates using default arguments to calculate a box’s volume. The function prototype for boxVolume (line 7) specifies that all three parameters have been given default values of 1. We provided variable names in the function prototype for readability. As always, variable names are **not required** in function prototypes.   * The first call to boxVolume (line 12) specifies no arguments, thus using all three default values of 1. The second call (line 16) passes only a length argument, thus using default values of 1 for the width and height arguments. The third call (line 20) passes arguments for only length and width, thus using a default value of 1 for the height argu- ment. The last call (line 24) passes arguments for length, width and height, thus using no default values. * Using default arguments can simplify writing function calls. However, some programmers feel that explicitly specifying all arguments is clearer. --- ## 6.16 Unary Scope Resolution Operator * It’s possible to declare local and global variables of the same name. * C++ provides the **unary scope resolution operator** (`::`) to access a global variable when a local variable of the same name is in scope. The unary scope resolution operator cannot be used to access a local vari- able of the same name in an outer block. A global variable can be accessed directly without the unary scope resolution operator if the name of the global variable is not the same as that of a local variable in scope.  * Always using the **unary scope resolution operator** (`::`) to refer to global variables makes programs easier to read and understand, because it makes it clear that you’re intending to access a global variable rather than a nonglobal variable. * Always using the unary scope resolution operator (::) to refer to global variables makes programs easier to modify by reducing the risk of name collisions with nonglobal variables. * Always using the unary scope resolution operator (::) to refer to a global variable elimi- nates logic errors that might occur if a nonglobal variable hides the global variable. * Avoid using variables of the same name for different purposes in a program. Although this is allowed in various circumstances, it can lead to errors. --- ## 6.17 Function Overloading * C++ enables several functions of the same name to be defined, as long as they have differ- ent signatures. This is called **function overloading**. * The C++ compiler selects the proper function to call by examining the number, types and order of the arguments in the call. Function overloading is used to create several functions of the same name that perform similar tasks, but on different data types. * For example, many functions in the math library are overloaded for different numeric types—the C++ standard requires float, double and long double overloaded versions of the math library functions discussed in Section 6.3. ### Overloaded square Functions    ### How the Compiler Differentiates Overloaded Functions * Overloaded functions are distinguished by their signatures. A signature is a combination of a function’s name and its parameter types (in order).    * The compiler uses only the parameter lists to distinguish between overloaded func- tions. Such functions need not have the same number of parameters. Use caution when overloading functions with default parameters, because this may cause ambiguity. # 6.18 Function Templates * Overloaded functions are normally used to perform similar operations that involve differ- ent program logic on different data types. If the program logic and operations are identical for each data type, overloading may be performed more compactly and conveniently by using **function templates**. * You write a single function template definition. Given the argument types provided in calls to this function, C++ automatically generates separate function template specializations to handle each type of call appropriately. Thus, defining a single function template essentially defines a whole family of overloaded functions. * All function template definitions begin with the **template keyword** (line 3) followed by a template parameter list to the function template enclosed in angle brackets (< and >). * Every parameter in the template parameter list (often referred to as a formal type parameter) is preceded by keyword typename or keyword class (they are synonyms in this context). * The formal type parameters are placeholders for fundamental types or user-defined types. These placeholders, in this case, T, are used to specify the types of the function’s parameters (line 4), to specify the function’s return type (line 4) and to declare variables within the body of the function definition (line 6). * A function template is defined like any other function, but uses the formal type parameters as placeholders for actual data types.  * The function template declares a single formal type parameter `T` (line 3) as a placeholder for the type of the data to be tested by function maximum. The name of a type parameter must be unique in the template parameter list for a particular template definition. When the compiler detects a maximum invocation in the program source code, the type of the data passed to maximum is substituted for T throughout the template definition, and C++ creates a complete function for determining the maximum of three values of the specified data type—all three must have the same type, since we use only one type parameter in this example. Then the newly created function is compiled. Thus, templates are a means of code generation.     --- ## 6.19 Recursion * For some problems, it’s useful to have functions call themselves. A **recursive function** is a function that calls itself, either directly, or indirectly (through another function). * Recursive problem-solving approaches have a number of elements in common. A recursive function is called to solve a problem. The function knows how to solve only the **simplest case(s)**, or so-called **base case(s)**. If the function is called with a base case, the function simply returns a result. If the function is called with a more complex problem, it typically divides the problem into two conceptual pieces—a piece that the function knows how to do and a piece that it does not know how to do. * To make recursion feasible, the latter piece must resemble the original problem, but be a slightly simpler or smaller version. This new problem looks like the original, so the function calls a copy of itself to work on the smaller problem—this is referred to as a recursive call and is also called the recursion step. The recursion step often includes the keyword return, because its result will be combined with the portion of the problem the function knew how to solve to form the result passed back to the original caller, possibly `main`. * The factorial of a nonnegative integer n, written *n!* (and pronounced “n factorial”), is the product  with 1! equal to 1, and 0! defined to be 1. * For example, 5! is the product 5 · 4 · 3 · 2 · 1, which is equal to 120. The factorial of an integer, number, greater than or equal to 0, can be calculated iteratively (nonrecursively) by using a for statement as follows:  * A recursive definition of the factorial function is arrived at by observing the following algebraic relationship:  * For example, 5! is clearly equal to 5 * 4! as is shown by the following:   * Figure 6.29 uses recursion to calculate and print the factorials of the integers 0–10. (The choice of the data type unsigned long is explained momentarily.)  --- ## Example Using Recursion : Fibonacci series * The Fibonacci series  * The Fibonacci series can be defined recursively as follows:    ### Order of Evaluation of Operands * Most programmers simply assume that the operands are evaluated left to right. C++ does not specify the order in which the operands of most operators (including +) are to be evaluated. Therefore, you must make no assumption about the order in which these calls execute. * C++ specifies the order of evaluation of the operands of only four operators—`&&`, `||`, comma (`,`) and `?:`. The first three are binary operators whose two operands are guaranteed to be evaluated left to right. The last operator is C++’s only ternary operator—its leftmost operand is always evaluated first; if it evaluates to nonzero (true), the middle operand evaluates next and the last operand is ignored; if the leftmost operand evaluates to zero (false), the third operand evaluates next and the middle operand is ignored. --- # 6.21 Recursion and Iteration * Both iteration and recursion are based on a control statement: Iteration uses a repetition structure; recursion uses a selection structure. * Both iteration and recursion involve repetition: Iteration explicitly uses a repetition structure; recursion achieves repetition through repeated function calls. * Iteration and recursion both involve a termination test: Iteration terminates when the loop-continuation condition fails; recursion terminates when a base case is recognized. * Iteration with counter-controlled repetition and recursion both gradually approach termination: Iteration modifies a counter until the counter assumes a value that makes the loop-continuation condition fail; recursion produces simpler versions of the orig- inal problem until the base case is reached. * Both iteration and recursion can occur infinitely: An infinite loop occurs with iteration if the loop-continuation test never becomes false; infinite recursion occurs if the recursion step does not reduce the problem during each recursive call in a manner that converges on the base case.   * Recursion has negatives. It repeatedly invokes the mechanism, and consequently the overhead, of function calls. This 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; this can consume considerable memory. Iteration normally occurs within a function, so the overhead of repeated function calls and extra memory assignment is omitted. So why choose recursion? * Any problem that can be solved recursively can also be solved iteratively (nonrecursively). A recursive approach is normally chosen when the recursive approach more naturally mirrors the problem and results in a program that’s easier to understand and debug. Another reason to choose a recursive solution is that an iterative solution is not apparent.