练基本功recursion （在Jupyter Notebook，python 3）写Boggle（:

!pip install pyspellchecker
from spellchecker import SpellChecker

#create a spell checker instance
spell = SpellChecker()

#range over each possible combination with for loop and recursion.
def go(input_string, origin, word, letter_count, dic):
  #the base case
  if letter_count == 0 and ''.join(spell.known([word + input_string])) not in dic and len(''.join(spell.known([word + input_string]))) > 1:
    dic[len(dic)] = ''.join(spell.known([word + input_string]))   

  for i in range(letter_count): #add each letter of input_string to each position in word
    #check word + input_string[i]
    if ''.join(spell.known([word + input_string[i]])) not in dic and len(''.join(spell.known([word + input_string[i]]))) > 1:
       dic[len(dic)] = ''.join(spell.known([word + input_string[i]]))      

    go(input_string[:i] + input_string[i+1:],origin, word+input_string[i], letter_count-1, dic) #use recursion to work as nested for loops

  if letter_count == origin:
      for j in dic:
        print(dic[j])
      
#to process input
def boggle(input_string):
   go(input_string, len(input_string), "", len(input_string), {})

boggle("adieu")

一开始用return发现无法会跳出循环就用print了
以下是改进的代码，（刚发现recursion不一定用base case），可能还能改进，先把input_string放在dic里，最后for i in range（len（dic）-1）:
print(dic[i+1])

#no base case
!pip install pyspellchecker
from spellchecker import SpellChecker

#create a spell checker instance
spell = SpellChecker()

#range over each possible combination with for loop and recursion.
def go(input_string, origin, word, letter_count, dic):
  
  for i in range(letter_count): #add each letter of input_string to each position in word
    #check word + input_string[i]
    if ''.join(spell.known([word + input_string[i]])) not in dic and len(''.join(spell.known([word + input_string[i]]))) > 1:
       dic[len(dic)] = ''.join(spell.known([word + input_string[i]]))      

    go(input_string[:i] + input_string[i+1:],origin, word+input_string[i], letter_count-1, dic) #use recursion to work as nested for loops

  if letter_count == origin:
      for j in dic:
        print(dic[j])
      
#to process input
def boggle(input_string):
   go(input_string, len(input_string), "", len(input_string), {})

boggle("adieu")

规则是用给定单词的字母拼出新单词，原词同一个位置的字母不能用两次，长度不定（当然不超过原词长度）

新人求米188看面经，谢谢