上海交通大学：《程序设计基础》课程教学讲义（密西根学院）Lecture Notes_19 Recursion 1

上海交通大学交大密西根 ■■ 联合学院·一 ◆] 181 UM-SJTU Joint Institute University of Michigan Shanghal Jiao Tong University Vg 101:Introduction To Computer and Programming Recursion

Vg 101: Introduction To Vg 101: Introduction To Computer and Programming Computer and Programming Recursion

上海交通大学交大密西根 联合学院· UM-SJTU Joint Institute University of Michigan Shanghal Jiao Tong University What? Most algorithmic strategies used to solve programming problems have counterparts out side the domain of computing.E.g,when you perform a task repeatedly, you are using iteration.When you make a decision,you exercise conditional control. Because these operations are familiar,most students learn to use the control statements for,while and if with relatively little trouble. However,you will have to learn to use a powerful problem-solving strategy that has few direct counterparts in the real world. That strategy is called recursion!

What? • Most algorithmic strategies used to solve programming problems have counterparts out side the domain of computing. E.g, when you perform a task repeatedly, you are using iteration. When you make a decision, you exercise conditional control. • Because these operations are familiar, most students learn to use the control statements for, while and if with relatively little trouble. • However, you will have to learn to use a powerful problem-solving strategy that has few direct counterparts in the real world. • That strategy is called recursion!

上海交通大学交大密西根 联合学院·一 ■ UM-SJTU Joint Institute University of Michigan Shanghal Jiao Tong University What is and what is not? Recursion is a solution technique in which large problems are solved by reducing them to smaller problems of the same form. ● Notice:the italicized phrase is crucial to the definition.Otherwise it describes the basic strategy of stepwise refinement.Both strategies involve decomposition. What makes recursion special is that the sub- problems in a recursive form have the same form as the original while stepwise refinement is not

What is and what is not? What is and what is not? • Recursion is a solution technique in which large problems are solved by reducing them to smaller problems of the same form . • Notice: the italicized phrase is crucial to the definition. Otherwise it describes the basic strategy of stepwise refinement. Both strategies involve decomposition. • What makes recursion special is that the sub￾problems in a recursive form have the same form as the original while stepwise refinement is not

上海交通大学交大密西根 联合学院一 ◆ 81 UM-SJTU Joint Institute University of Michigan Shanghal Jiao Tong University A Simple Problem We will start our Recursion discussion of Problem:Print the characters of recursion with a a string,one per line simple problem: Input: “Vg101” Output: ·print the characters g 1 0 1

A Simple Problem A Simple Problem • We will start our discussion of recursion with a simple problem: • print the characters Recursion Problem: Print the characters of a string, one per line Input: “Vg 101” Output: V g 1 0 1

上海交通大学交大密西根 联合学院·一 ◆ 181 UM-SJTU Joint Institute ■ University of Michigan Shanghal Jiao Tong University Pseudocode Here is some pseudocode that would seem to do the job,even if it is a little vague. Recursion void printStr (string &str) { if the string is empty,return Print the first character Print the rest as a short string

Pseudocode Pseudocode • Here is some pseudocode that would seem to do the job, even if it is a little vague. Recursion void printStr (string &str) { if the string is empty, return Print the first character Print the rest as a short string }

上海交通大学交大密西根 联合学院·一 181t UM-SJTU Joint Institute University of Michigan Shanghal Jiao Tong University The First Part of the Code The first part is easy to turn into real C++. void printStr (string str) ConsoleT console; if (Istr.empty ( { console.printLine (strLOJ,endl); i

The First Part of the Code The First Part of the Code • The first part is easy to turn into real C++

上海交通大学交大密西根 ·联合学院一 ■ 81 UM-SJTU Joint Institute University of Michigan Shanghal Jiao Tong University Recursion code Now for the void printStr(string str) conceptual leap:we ConsoleT console; can use the same if (Istr.empty ( { function we are console.printLine(str[0],endl); defining to solve the printstr (str.substr(1,str.length()); rest of the problem! That is,we can print This is a simpler problem and the rest of the string it has the same form and by having PrintString it will converge at finite steps of call itself. iterations

Recursion Code Recursion Code • Now for the conceptual leap: we can use the same function we are defining to solve the rest of the problem! • That is, we can print the rest of the string by having PrintString call itself. • This is a simpler problem and • it has the same form and • it will converge at finite steps of iterations

上海交通大学交大密西根 联合学院·一 ◆ UM-SJTU Joint Institute University of Michigan Shanghal Jiao Tong University Conditions of Using Recursion Strategy The two essential conditions void printStr (string str) in which recursion can be ConsoleT console; used are You must be able to if (Istr.empty ( identify the simple cases for { which the answer is easily console.printLine(str[0],endl); determined. printstr(str.substr (1,str.length () } You must be able to identify a recursive decomposition that allows This is a simpler problem and you to break any complex instance of the problem it has the same form and into simpler problems of it will converge at finite steps of the same form. iterations

Conditions of Using Recursion Strategy Conditions of Using Recursion Strategy • The two essential conditions in which recursion can be used are : – You must be able to identify the simple cases for which the answer is easily determined. – You must be able to identify a recursive decomposition that allows you to break any complex instance of the problem into simpler problems of the same form. • This is a simpler problem and • it has the same form and • it will converge at finite steps of iterations

上海交通大学交大密西根 ·联合学院一 81 UM-SJTU Joint Institute University of Michigan Shanghal Jiao Tong University Recursion Paradigm In general,the body of a recursive function has the following form: if(test for simple case) { Compute a simple solution without recursion. } else { Break the problem down into subproblems of the same form. Solve each of the subproblems by calling this function recursively. Reassemble the solutions to the subproblems into a solution for the whole

Recursion Paradigm Recursion Paradigm • In general, the body of a recursive function has the following form: if (test for simple case) { Compute a simple solution without recursion. } else { Break the problem down into subproblems of the same form. Solve each of the subproblems by calling this function recursively. Reassemble the solutions to the subproblems into a solution for the whole. }

上海交通大学交大密西根 ·联合学院一 181 UM-SJTU Joint Institute ■ University of Michigan Shanghal Jiao Tong University Code of Example 1 int main O string str "Vg 101"; printstr (str); return 0; void printStr (string str) ConsoleT console; if (Istr.empty ( console.printLine (str[O],endD; printstr (str.substr (1,str.length () ;

Code of Example 1 Code of Example 1