"Write a recursive function called anagram(s) that returns a list of all the possible anagrams of the string, s." Can I get some guidance on how to tackle this question? I am new to recursion and do not understand how to make a simpler base case for this scenario. Or what my general algorithm would be.

CodePudding user response：

I linked a duplicate question in comments above which contains an implementation of this, but since this is clearly a homework-like task I'd encourage you to use it as a last resort.

Your end goal is a list of all possible combinations of the letters in a given string.

When looking for a recursive approach, you want to be thinking about "how can I break this task down into doing the same thing over and over again, against increasingly simple versions of the input."

So instead of trying to anagram the full string ABCD, start out by just anagramming the first letter: you'll have one set of results that starts with "A" (and has all the combinations of "BCD" after it), one that starts with "B" (and is followed by all the combinations of "ACD"), and so on for C and D.

So that's the first layer of your recursion; pluck each letter out one by one as the first character and recurse with the remainder of the string.

The first instance of the next layer only has to deal with a three character string "BCD" -- you know all of these will start with "A", and you'll need to recurse for "B", "C", and "D" as the second letter, with the remaining letters left to be shuffled.

One layer deeper, you're starting with (for example) "AB", and need to recurse against both the possible orderings of "CD".

The bottom layer of the recursion will be when there's only a single letter left so there's nothing left to shuffle; at that point you can just append it to the preceding characters and return the result to be added to your list of anagrams.

Your recursive function would take two parameters: the first one is "the letters I've already shuffled" and the second one is "the letters I have yet to shuffle".