縦型探索2

再帰ありバージョン。
どうも再帰あり版じゃないとだめっぽいので。

#!/usr/bin/python
# -*- coding: utf-8 -*-
import random

def endTest(answer):

	str = ""
	for a in answer:
		str += a
	
	print str
	if str == "yystartABD":
		return True
	return False

def getNextCandidate(now,mt):
	sets = set("")
	for m in mt[now]:
		sets.add(m)
	return sets
	
def vSearch(count,now,mt,answer):
	# mt マルコフテーブル
	# cand は mapあたり
	cand = getNextCandidate(now,mt)
	while True:
		print "now",
		print now,
		print "answer",
		print answer,
		print "cand",
		print cand
		raw_input()
		
		# candが空になったらcandidateStackから引っ張り出す
		while len(cand) == 0:
			answer.pop(-1)
			return False,""

		while True:
			next = random.choice(mt[now])
			print "next",
			print next
			
			candFlag = False
			for a in cand:
				if next == a:
					candFlag = True
					break
			if candFlag == True: break

		cand.remove(next)
		answer.append(now)
		if next == "yyend" or count > 30 :
			if endTest(answer) == True:
				answer.append(next)
				return True,answer
			else:
				print "false"
				answer.pop(-1)
				continue
		
		result, ans = vSearch(count+1,next,mt,answer)
		if result == True:
			return True, ans

if __name__ == "__main__":
	mt = {}
	mt["yystart"] = ["A"]
	mt["A"] = ["B","F"]
	mt["B"] = ["C","D","E"]
	mt["C"] = ["yyend"]
	mt["D"] = ["yyend"]
	mt["E"] = ["yyend"]
	mt["F"] = ["C","G"]
	mt["G"] = ["yyend"]
	mt["yyend"] = []
	answer = []
	count = 0
	now = "yystart"
	cand = getNextCandidate(now,mt)
	
	print vSearch(0,now,mt,answer)