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