时间戳

首页 > 解决方案 > Python递归函数不返回

python - Python递归函数不返回

问题描述

我正在尝试编写一个递归函数，它返回单词在排序单词列表中的位置，或者None在找不到单词时返回。以下是代码：

def partition(t,kw,upper,lower):
    if ((upper-lower) > 1):
        pivot = lower + (upper-lower)//2
        print("pivot is now {}".format(pivot))
        if (kw >= t[pivot]):
            lower = pivot
            print("searching on the right",upper,lower)
            return(partition(t,kw,upper,lower))
        
        elif (kw <= t[pivot-1]):
            upper = pivot-1
            print("searching on the left",upper,lower)
            return(partition(t,kw,upper,lower))

        else:
            return None 
            #that means the keyword is between t[pivot-1] and t[pivot]
            #which means it doesnt exist in the list
    if (upper - lower) <= 1:
        if (kw == t[upper]):
            print("found element {} at upper bound {}".format(kw,upper))
            return(upper)
        elif (kw == t[lower]):
            print("found element {} at lower bound {}".format(kw,lower))
            return(lower)
        else:
            return None

def search(t, kw):
    u = len(t)
    partition(t,kw,u,0)

如您所见，每当我调用它时，我都会返回该函数（不返回是使用递归调用的常见错误）。同时，这是我使用的示例数组：

['', '', '150', '150', '1997,with', '36', '49', 'An', 'Annotated', 'Annotation', 'Bibliography', 'China', 'Chinese', 'Chinese', 'Classical', 'During', 'Dynasty', 'Hong', 'Hong', 'Hong', 'Hong', 'Hong', 'In', 'It', 'Kong', 'Kong', 'Kong', 'Kong,', 'Kong.', 'Mainland', 'Poets', 'Qing', 'They', 'Together,', 'Writings', 'a', 'a', 'a', 'a', 'a', 'active', 'activity,', 'addition', 'almost', 'and', 'and', 'and', 'and', 'and', 'and', 'annotations', 'anthologies', 'basic', 'been', 'before.', 'bibliographic', 'bibliographies,', 'by', 'carry', 'ci-poetry', 'ci-poetry', 'classical', 'collected', 'commentaries', 'compilation,', 'compilations', 'compiled', 'covered,', 'development', 'events', 'focused', 'form', 'form', 'formation,', 'from', 'from', 'has', 'help', 'hidden', 'in', 'in', 'in', 'in', 'includes', 'individual', 'information', 'information', 'introduces', 'invaluable', 'is', 'late', 'literary', 'literati', 'literature', 'literature.', 'membership,', 'most', 'never', 'not', 'of', 'of', 'of', 'of', 'of', 'of', 'of', 'of', 'of', 'of', 'offer', 'on', 'on', 'on', 'on', 'order', 'over', 'past', 'periods', 'pioneer', 'pity', 'poetic', 'poetry', 'poetry', 'poetry', 'poet’s', 'political', 'previous', 'previously', 'published', 'refuge', 'research', 'sequel', 'shi-', 'shi-', 'societies', 'societies', 'societies', 'societies.', 'societies.', 'splendor,', 'that', 'that', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'these', 'these', 'these', 'this', 'times', 'to', 'to', 'to', 'to', 'to', 'to', 'took', 'tools', 'topic', 'tradition.', 'turmoil', 'two', 'uncover', 'understand', 'understanding', 'unique', 'up', 'various', 'very', 'volume,', 'which', 'works,', 'worthwhile', 'would', 'years,']

我在搜索这个词"Qing"，它应该排在第 31 位。现在似乎该函数可以找到我需要的单词，但无法返回：

the result is
pivot is now 92
searching on the left 91 0
pivot is now 45
searching on the left 44 0
pivot is now 22
searching on the right 44 22
pivot is now 33
searching on the left 32 22
pivot is now 27
searching on the right 32 27
pivot is now 29
searching on the right 32 29
pivot is now 30
searching on the right 32 30
pivot is now 31
searching on the right 32 31
found element Qing at lower bound 31
None

我尝试搜索与递归函数相关的问题，但似乎没有太多相关内容。SO上的大多数帖子都是由于没有返回递归函数引起的，我真的不确定这里出了什么问题。

标签： pythonrecursion

解决方案

您的功能似乎正在运行。我想你只是忘了从搜索返回，即

def search(t, kw):
    u = len(t)
    lower = partition(t,kw,u,0)
    return lower

输出

...
searching on the right 32 30
pivot is now 31
searching on the right 32 31
found element Qing at lower bound 31
31

推荐阅读