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 Simply write number n to screen Recursive 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 ¨ Simply write number n to screen ¨ Recursive 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