上海交通大学交大密西根 ■■ 联合学院·一 ◆] 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 subproblems 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 }