Question

I'm doing the ocw version and i don't understand how to do the recursive part of ps4. the solutions for ps4 include a pseudocode for it but i'm still too confused to do it. The solution files don't have any solution code for find_best_shifts_rec().
so not only do i feel stupid, i don't even have a way to figure it out and move on. is there somewhere I'm missing that shows you the solution for it?
edit: it looks like they uploaded the wrong version of the solutions since the ps4recursion solution is unrelated to the problemset

Answer 1

Recursion solves part of a problem in each of it's "iterations". The main thing to remember when writing recursive functions is to have a base case. The base case is when to stop recursing and start unwinding. A recursive function for converting numbers from base 10 to other bases, in Python:

characters = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def mkDigit( number, base ):
if( number == 0 ):
return ""
index = number % base
number = number // base
return mkDigit( number, base ) + characters[ index ]

Answer 2

you can take mine for reference, but i got a problem of "maximum recursion depth exceeded" when n > 8

def find_best_shifts_rec(wordlist, text, start):
TempText = text[start:]
for i in range(27):
flag = True
index = 0
shiftText = apply_shift(TempText, i)
for word in shiftText.split(' '):
if not is_word(wordlist, word):
flag = False
if index == 0:
break
else:
l = find_best_shifts_rec(wordlist, text[:start] + shiftText, len(text[:start]) + shiftText.find(word))
if l == None:
break
else:
return [(start, i)] + l
index += 1

if flag == True: # it means all words in current shift are valid, then we can return the sequence
return [(start, i)]
# if all shift can't return valid value, then we consdier it as a fail
return None

Answer 3

i appreciate the help. I still cannot get the structure anywhere near close enough that it runs through and triggers all of the parts properly. It would help if the class would've went over an example of recursion that was non-trivial. it's easy to understand the structure of simple ones but this is just too confusing.

Answer 4

also i'm still unclear as what the base case is and the pseudo code provided in the solutions doesn't really make it clear to me either so if i have that wrong i'm never gonna be able to fix it.

Answer 5

OK this is the closest I can get but it's clearly not performing recursion properly or adjusting the list right:

for shift in range(27):
print '---'
print 'shift ', shift
## beginning to startpoint/unshifted partial text
s1 = text[0:start]
print 's1', s1
## startoint to end/shifted partial text
s2 = apply_shift(text[start:], shift)
print 's2', s2
## combine
s = s1 + s2
print 's', s
## check for the next space, if none is found, == =1
isaspace = s2.find(' ')
print 'isaspace', isaspace
## if there IS another space -and- text from startpoint to that space is a word
if isaspace > -1 and is_word(wordlist, s2[:isaspace]):
####recursively run ##index-s ofnextspace##
posslist = find_best_shifts_rec(wordlist, s, len(s1) + isaspace + 1)
print 'posslist', posslist, type(posslist)
## if it found the end properly and returned a list to posslist
if type(posslist) == list:
print '(', start, shift, ')'
tup = start, shift
return posslist.insert(0, tup)
if posslist == None:
print 'brk'
break
## if there is NOT another space (last word)
if isaspace == -1:
## AND the last word Is a real word
if is_word(wordlist, s2):
print 'last'
print ' base ', [(start, shift)]
return [(start, shift),]
print 'next shift'
return None

Answer 6

hi, i've modified my solution, and it works fine now, please take a look:

def find_best_shifts_rec_without_comment(wordlist, text, start):
for i in range(27):
s = text[:start] + apply_shift(text[start:], i)
index = s.find(' ', start)
if index != -1:
if is_word(wordlist, s[start:index]):
l = find_best_shifts_rec(wordlist, s, index + 1)
if l != None:
return [(start, i)] + l
else:
continue
else:
if is_word(wordlist, s[start:]):
return [(start, i)]
return None

#for every possible shift we apply shift with the text from start to the end
#if we find a ' '(blank) in our shifted text means we may get a valid word
#if we get a valid word with current shift, continue to do next shift after this word.
#if we get a shift sequence, we add current shift and return to our caller.
#if we reach the end and the last word is valid, we return current shift
#if all shift can't get a valid return, we failed in this path

Answer 7

BTW, i've checked your code, just modify "if posslist == None: break" to "if posslist == None: continue" would solve your problem

Answer 8

thank you so much for helping me. Your code works perfectly except if you have more words than shifts applied to them, it adds extra tuples to your returned list of shift 0. if you replace each of your return statements with conditional returns :

if shift != 0: return [(start, shift)] + l
else: return l

THANK YOU so very much for posting your code though I could not figure out how to do it, I was closer than I thought at least.

Answer 9

Thank you for pointing out that issue. I think we can learn together and help each other.