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