algorithm design and recursion traceback (most recent call last)file ""line in file ""line in reverse file ""line in reverse file ""line in reverse runtimeerrormaximum recursion depth exceeded 've only shown portion of the outputit actually consisted of lineswhat' happened hererememberto build correct recursive function we need base case for which no recursion is requiredotherwise the recursion is circular in our haste to code up the functionwe forgot to include base case what we have written is actually an infinite recursion every call to reverse contains another call to reverseso none of them ever return of courseeach time function is called it takes up some memory (to store the parameters and local variables)so this process can' go on forever python puts stop to it after callsthe default "maximum recursion depth let' go back and put in suitable base case when performing recursion on sequencesthe base case is often an empty sequence or sequence containing just one item for our reversing problem we can use an empty string as the base casesince an empty string is its own reverse the recursive calls to reverse are always on string that is one character shorter than the originalso we'll eventually end up at an empty string here' correct version of reversedef reverse( )if =""return elsereturn reverse( [ :] [ this version works as advertised reverse("hello"'ollehexampleanagrams an anagram is formed by rearranging the letters of word anagrams are often used in word gamesand forming anagrams is special case of generating the possible permutations (rearrangementsof sequencea problem that pops up frequently in many areas of computing and mathematics let' try our hand at writing function that generates list of all the possible anagrams of string we'll apply the same approach that we used in the previous example by slicing the first character off of the string suppose the original string is "abc"then the tail of the string is "bcgenerating the list of all the anagrams of the tail gives us ["bc""cb"]as there are only two possible arrangements of two characters to add back the first letterwe need to place it in all possible positions in each of these two smaller anagrams["abc""bac""bca""acb""cab""cba"the first three anagrams come from placing "ain every possible place in "bc"and the second three come from inserting "ainto "cb