Reduce problem into smaller instances of same problem - recursive solution Recursive algorithm has two cases: Base/stopping case Recursive case, Ensure no infinite recursion. Use criteria to determine recursion correct | 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 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! 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 Recursive void Function: Vertical Numbers Task: display digits of . | 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 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! 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 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 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" Recursion—A Closer Look Computer tracks recursive calls Stops current function Must know results of
