Chapter 14Recursion2Overview14.1 Recursive Functions for Tasks 14.2 Recursive Functions for Values14.3 Thinking Recursively314.1Recursive Functions for Tasks4Recursive Functions for Tasks■A recursive function contains a call to itself■When breaking a task into subtasks, it may be that the subtask is a smaller example of the same task–Searching an array could be divided into searching the first and second halves of the array–Searching each half is a smaller version of searching the whole array–Tasks like this can be solved with recursive functions5Case Study: Vertical Numbers■Problem Definition:–void write_vertical( int n );//Precondition: n >= 0//Postcondition: n is written to the screen vertically// with each digit on a separate line6Case Study: Vertical Numbers■Algorithm design:–Simplest case: If n is one digit long, write the number–Typical case: 1) Output all but the last digit vertically 2) Write the last digit■Step 1 is a smaller version of the original task■Step 2 is the simplest case7Case Study: Vertical Numbers (cont.)■The write_vertical algorithm:–if (n < 10) { cout << n << endl; } else // n is two or more digits long { write_vertical(n with the last digit removed); cout << the last digit of n << endl; }8Case Study: Vertical Numbers (cont.)■Translating the pseudocode into C++–n / 10 returns n with the last digit removed ■124 / 10 = 12–n % 10 returns the last digit of n■124 % 10 = 4■Removing the first digit would be just as validfor defining a recursive solution–It would be more difficult to translate into C++91011Calls write_vertical(12)resumeOutput 3Function call endsTracing a Recursive Call■write_vertical(123)if (123 < 10) { cout << 123 << endl; } else// n is more than two digits { write_vertical(123/10); cout << (123 % 10) << endl; }12Calls write_vertical(1)resumeOutput 2Function call endsTracing write_vertical(12)■write_vertical(12)if (12 < 10) { cout << 12 << endl; } else// n is more than two digits { write_vertical(12/10); cout << (12 % 10) << endl; }13Simplest case is now trueFunction call endsOutput 1Tracing write_vertical(1)■write_vertical(1)if (1 < 10) { cout << 1 << endl; } else// n is more than two digits { write_vertical(1/10); cout << (1 % 10) << endl; }14A Closer Look at Recursion■write_vertical uses recursion–Used no new keywords or anything "new"–It simply called itself with a different argument■Recursive calls are tracked by–Temporarily stopping execution at the recursive call■The result of the call is needed before proceeding–Saving information to continue execution later–Evaluating the recursive call–Resuming the stopped execution15How Recursion Ends■Eventually one of the recursive calls must notdepend on another recursive call■Recursive functions are defined as–One or more cases where the task is accomplished by using recursive calls to do a smaller version of the task–One or more cases where the task is accomplished without the use of any recursive calls■These are called base cases or stopping cases16"Infinite" Recursion■A function that never reaches a base case, in theory, will run forever–In practice, the computer will run out of resources and the program will terminate abnormally17Example: Infinite Recursion■Function write_vertical, without the base case void new_write_vertical(int n) { new_write_vertical (n /10); cout << n % 10 << endl; }will eventually call write_vertical(0), which willcall write_vertical(0),which will call write_vertical(0), whichwill call write_vertical(0), which will call write_vertical(0), which will call write_vertical(0), which will call write_vertical (0), …18Stacks for Recursion■Computers use a structure called a stack to keep track of recursion–A stack is a memory structure analogous to a stack of paper■To place information on the stack, write it on a piece of paper and place it on top of the stack■To place more information on the stack, use a clean sheet of paper, write the information, and place it on the top of the stack■To retrieve information, only the top sheet of paper can be read, and thrown away when it is no longer needed19Last-in - First-out■A stack is a last-in-first-out memory structure–The last item placed is the first that can be removed■Whenever a function is called, the computer uses a "clean sheet of paper"–The function definition is copied to the paper–The arguments are plugged in for the parameters–The computer starts to execute the function body20Stacks and The Recursive Call■When execution of a function definition reaches a recursive call–Execution stops–Information is saved on a "clean sheet of paper" to enable resumption of execution later–This sheet of paper is placed on top of the stack–A new sheet is used for the recursive call■A new function definition is written, and arguments are plugged into parameters■Execution of the recursive call begins21The Stack and Ending Recursive Calls■When a recursive function call is able to complete its computation with no recursive calls–The computer retrieves the top "sheet of paper" from the stack and resumes computation based on the information on the sheet–When that computation ends, that sheet of paper is discarded and the next sheet of paper on the stack is retrieved so that processing can resume–The process continues until no sheets remain in the stack22Activation Frames■The computer does not use paper■Portions of memory are used –The contents of these portions of memory is called an activation frame■The activation frame does not actually contain a copy of the function definition, but references a single copy of the function23Stack Overflow■Because each recursive call causes an activation frame to be placed on the stack–infinite recursion can force the stack to grow beyond its limits to accommodate all the activation frames required–The result is a stack overflow–A stack overflow causes abnormal termination of the program24■Any task that can be accomplished using recursion can also be done without recursion–A nonrecursive version of a function typically contains a loop or loops–A non-recursive version of a function is usually called an iterative-version –A recursive version of a function■Usually runs slower■Uses more storage■May use code