Recursion For Programmers

Huw’s courses are great. He explains everything clearly and it’s easy to remember what you’ve learned. Even if you have experience you always learn something useful.

I feel that this course was just the right length. It was helpful, and I am sure I will be returning to it from time–to–time for reference.

Well , first of all kudos to instructor to think about having a course on recursion.If anyone wants to get a good overview of this topic , this is nice course to start with. If the subject of tree data structure is also covered in depth, which is a natural case of recursion and bit more advanced application of recursion , that would be wonderful.

Misses some stuff.. still wont be able to figure out how merge sort and such stuff works.. :/

Good explanations, concise and clear.

I wish there was a deeper explanation of the directory navigation program! Otherwise – I wouldn’t say recursion clicked immediately for me but it cleared up some confusion around the concept with respect to scoping.

I miss the visualizations of the scopes, like you can see in Python Tutor. Hopefully this will come. Also I don’t understand when all courses do fibronacially, it has to be done here. I would suggest to do a fibernaccio with letters or whatever. Also I would have expected examples of problems to see HOW you could rewrite them with pseudocode to recursive program. To be honest, the courses about recursive programming in MIT edx introduction to scientific programming give a better view in Recursive programming. But that maybe has to do with the fact that this course is already dated (old) (?). Also I was suprised that the term base case never was mentioned. So, I was hoping to be able to learn how to solve this problem beneath. And that’s was not really part of this course. Problem Set 4 Handed out : October 5, 2016 Due: October 12, 2016 @ 11:59 PM This problem set has two parts. The first part allows you to practice thinking about problems in a recursive fashion, taking advantage of the idea that one can reduce the problem to a simpler version of the same problem. In ps4a.py , you will write a recursive function that takes as input a string and figures out all the possible reorderings of the characters in the string. The second part will give you experience in thinking about problems in terms of classes, each instance of which contains specific attributes as well as methods for manipulating them. In ps4b.py , you will use object–oriented programming to write a Caesar/shift cipher. In ps4c.py , you will use object–oriented programming to write a very simple substitution cipher. As always, please do not rename the files we provide you with, change any of the provided helper functions, change function/method names, or delete provided docstrings. You will need to keep words.txt and story.txt in the same folder in which you store ps4a.py, ps4b.py and ps4c.py . Finally, please consult the Style Guide on as we will be taking point deductions for violations (e.g. non–descriptive variable names and uncommented code). For this pset style guide numbers 6, 7 and 8 will be highly relevant so make sure you go over those before starting the pset, and again before you hand it in! Part A: Permutations of a string A permutation is simply a name for a reordering. So the permutations of the string abc are abc , acb , bac , bca , cab , and cba . Note that a sequence is a permutation of itself (the trivial permutation). For this part of the pset you ll need to write a recursive function get permutations that takes a string and returns a list of all its permutations. You will find this function helpful later in the pset for part C. A couple of notes on the requirements: Recursion MUST be used , global variables may NOT be used. Additionally, it is okay to use loops to code the solution. The order of the returned permutations does not matter. Please also avoid returning duplicates in your final list. 1 Suggested Approach In order to solve any recursive problem, we must have at least one base case and a recursive case (or cases). We can think of our base case as the simplest input we could have to this problem (for which determining the solution is trivial and requires no recursion) –– for this approach, our base case is if sequence is a single character (there s only one way to order a single character). If sequence is longer than one character, we need to identify a simpler version of the problem that, if solved, will help us easily find all permutations for sequence . The pseudocode below gives one approach to recursively solving this problem. Given an input string sequence : Base case: if sequence is a single character, there s only one way to order it return a singleton list containing sequence Recursive case: suppose we have a method that can give us a list of all permutations of all but the first character in sequence (Hint: think recursion) then the permutations of all characters in sequence would be all the different ways we can insert the first character into each permutation of the remaining characters example: if our word was bust , we hold out the character b and get the list [ ust , sut , stu , uts , tus , tsu ] then ust gives us: b ust , u b st , us b t , ust b sut gives us: b sut , s b ut , su b t , sut b and so on …