Chapter 13 ABSOLUTE C++ Recursion WALTER SAVITCH SECOND EDITION PEARSON Copyright2006 Pearson Addison-Wesley All rights reserved
Chapter 13 Recursion
Learning Objectives Recursive void Functions Tracing recursive calls Infinite recursion,overflows Recursive Functions that Return a value ◆Powers function Thinking Recursively Recursive design techniques ◆Binary search Copyright006 Pearson Addison-Wesley.All rights reserved. 13-2
Copyright © 2006 Pearson Addison-Wesley. All rights reserved. 13-2 Learning Objectives ¨ Recursive void Functions ¨Tracing recursive calls ¨Infinite recursion, overflows ¨ Recursive Functions that Return a Value ¨Powers function ¨ Thinking Recursively ¨Recursive design techniques ¨Binary search
Introduction to Recursion A function that "calls itself" ◆Said to be recursive In function definition,call to same function ◆C++allows recursion As do most high-level languages Can be useful programming technique ◆Has limitations Copyright 2006 Pearson Addison-Wesley.All rights reserved. 13-3
Copyright © 2006 Pearson Addison-Wesley. All rights reserved. 13-3 Introduction to Recursion ¨ A function that "calls itself" ¨Said to be recursive ¨In function definition, call to same function ¨ C++ allows recursion ¨As do most high-level languages ¨Can be useful programming technique ¨Has limitations
Recursive void Functions ◆Divide and Conquer Basic design technique Break large task into subtasks Subtasks could be smaller versions of the original task! ◆Vhen they are→recursion Copyright006 Pearson Addison-Wesley.All rights reserved. 13-4
Copyright © 2006 Pearson Addison-Wesley. All rights reserved. 13-4 Recursive void Functions ¨ Divide and Conquer ¨Basic design technique ¨Break large task into subtasks ¨ Subtasks could be smaller versions of the original task! ¨When they are recursion
Recursive void Function Example ◆Consider task: Search list for a value Subtask 1:search 1st half of list Subtask 2:search 2nd half of list Subtasks are smaller versions of original task! When this occurs,recursive function can be used. Usually results in "elegant"solution Copyright 2006 Pearson Addison-Wesley.All rights reserved. 13-5
Copyright © 2006 Pearson Addison-Wesley. All rights reserved. 13-5 Recursive void Function Example ¨ Consider task: ¨ Search list for a value ¨ Subtask 1: search 1st half of list ¨ Subtask 2: search 2nd half of list ¨ Subtasks are smaller versions of original task! ¨ When this occurs, recursive function can be used. ¨ Usually results in "elegant" solution
Recursive void Function: Vertical Numbers Task:display digits of number vertically, one per line ◆ Example call: writeVertical(1234); Produces output: 1 2 3 4 Copyright 2006 Pearson Addison-Wesley.All rights reserved. 13-6
Copyright © 2006 Pearson Addison-Wesley. All rights reserved. 13-6 Recursive void Function: Vertical Numbers ¨ Task: display digits of number vertically, one per line ¨ Example call: writeVertical(1234); Produces output: 1 2 3 4
Vertical Numbers: Recursive Definition Break problem into two cases Simple/base case:if n=10,two subtasks: 1-Output all digits except last digit 2-Output last digit ◆ Example:argument 1234: 1st subtask displays 1,2,3 vertically 2nd subtask displays 4 Copyright 2006 Pearson Addison-Wesley.All rights reserved. 13-7
Copyright © 2006 Pearson Addison-Wesley. All rights reserved. 13-7 Vertical Numbers: Recursive Definition ¨ Break problem into two cases ¨ Simple/base case: if n=10, two subtasks: 1- Output all digits except last digit 2- Output last digit ¨ Example: argument 1234: ¨ 1st subtask displays 1, 2, 3 vertically ¨ 2nd subtask displays 4
writeVertical Function Definition Given previous cases: void writeVertical(int n) if(n<10) //Base case cout <n <endl; else { //Recursive step writeVertical(n/10); cout <<(n%10)<<endl; Copyright006 Pearson Addison-Wesley.All rights reserved. 13-8
Copyright © 2006 Pearson Addison-Wesley. All rights reserved. 13-8 writeVertical Function Definition ¨ Given previous cases: void writeVertical(int n) { if (n < 10) //Base case cout << n << endl; else { //Recursive step writeVertical(n/10); cout << (n%10) << endl; } }
writeVertical Trace ◆Example call: writeVertical(123); writeVertical(12);(123/10) →writeVertical(1)；(12/10) →cout<<1<<endl; cout <2 <endl; cout <3 <endl; Arrows indicate task function performs Notice 1st two calls call again (recursive) Last call (1)displays and "ends" Copyright 2006 Pearson Addison-Wesley.All rights reserved. 13-9
Copyright © 2006 Pearson Addison-Wesley. All rights reserved. 13-9 writeVertical Trace ¨ Example call: writeVertical(123); writeVertical(12); (123/10) writeVertical(1); (12/10) cout << 1 << endl; cout << 2 << endl; cout << 3 << endl; ¨ Arrows indicate task function performs ¨ Notice 1st two calls call again (recursive) ¨ Last call (1) displays and "ends
Recursion-A Closer Look Computer tracks recursive calls Stops current function Must know results of new recursive call before proceeding Saves all information needed for current call ◆To be used later Proceeds with evaluation of new recursive call When THAT call is complete,returns to "outer"computation Copyright 2006 Pearson Addison-Wesley.All rights reserved. 13-10
Copyright © 2006 Pearson Addison-Wesley. All rights reserved. 13-10 Recursion—A Closer Look ¨ Computer tracks recursive calls ¨ Stops current function ¨ Must know results of new recursive call before proceeding ¨ Saves all information needed for current call ¨ To be used later ¨ Proceeds with evaluation of new recursive call ¨ When THAT call is complete, returns to "outer" computation