python - 递归如何跟踪答案？

Question

我正在 Hackerrank 上尝试这个挑战:https://www.hackerrank.com/challenges/the-power-sum/problem

有两种方法可以解决这个问题:

• 递归
• 动态规划

我的问题:我不明白递归解决方案的一部分。我不明白当它一直设置为零时它如何能够跟踪“答案”。

示例输入:

29

2

正确答案:2

示例输出:

cur 0
cur 0
cur 0
cur 0
the 0
cur 0
the 0
the 0
cur 0
cur 0
the 0
the 0
cur 0
the 0
cur 0
the 0
the 0
cur 0
cur 0
a match:
4 9 16 the 1
the 1
cur 0
the 1
a match:
4 25 the 2
the 2
cur 0
cur 0
the 0
the 2
cur 0
the 2
cur 0
the 2

代码:

import math
import os
import random
import re
import sys

def powerSum(x, n, value):
    s = sum (v**n for v in value)
    if s == x:
        print "a match:"
        for v in value:
            print v**n,
        return 1
    else:
        v = value[-1] + 1 if value else 1
        answer = 0
        print "cur", answer
        while s + v**n <= x:
            answer += powerSum(x, n, value+[v])
            v += 1
            print "the", answer
    return answer


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    x = int(raw_input())

    n = int(raw_input())

    value = []

    result = powerSum(x, n, value)

    fptr.write(str(result) + '\n')

    fptr.close()

Answer 1

您在问题中提供的代码以稍微复杂的方式实现了递归。就这些。考虑一下相同代码的不同版本:

def powerSum(x, n, value):

    answer = 0

    s = sum(v**n for v in value)
    # base case
    if s == x:
        answer = 1
    # recursive case
    else:
        v = value[-1] + 1 if value else 1
        while s + v**n <= x:
            answer += powerSum(x, n, value+[v])
            v += 1

    return answer