使用递归的范围(1，n,2)值之和

Question

我正在尝试将循环转换为递归算法。很简单，我只是无法让它在求和这些值时忽略n值，就像range一样。

这是迭代函数：

def function(n):
    total=0
    for i in range(1,n,2):
        total += i
    print(total)

function(5) # Output: 4

这是我尝试过的递归：

def function1(n):
    if n==1:
        return n
    else:
        return n+function1(n-2)
function(5) # Output: 9

因此，当function1应该忽略它时，它确实会与n相加。因为range()不包括停止号。

然后，我试着：

def f1(n):
    def f_recursive(n):
        if n==1 or n==2:
            return 1
        elif n==0:
            return 0
        else:
            return n + f_recursive(n - 2)

    return f_recursive(n) - n 

print(f1(5)) # Output: 4 Yeiii!!

但后来我意识到，这只适用于奇数。甚至都不会。如果是f1(6)，那么当它应该是9时，就得到了4，因为它最终是11-6= 9。

我太傻了，我试过：

def f1(n):
    def f_recursive(n):
        if n==1 or n==2:
            return 1
        elif n==0:
            return 0
        elif n%2 == 0:
            return n + f_recursive(n - 3)

        elif n%2 == 1:
            return n + f_recursive(n - 2)

    return f_recursive(n) - n 

print(f1(6))

当然也不起作用。我在这里没有正确理解递归吗？

Answer 1

棘手的部分是排除上限。如果上限是您唯一的参数n，则必须知道何时是第一个调用，何时是中间(递归)调用。或者，如果内部函数没有问题，您可以从1开始计数，直到您到达n。

def function1(n):
    def inner(i):
        return 0 if i >= n else i + inner(i + 2)
    return inner(1)

Answer 2

递归的问题是返回的是n，而不是当前所在的范围(列表)中的值，这造成了一个问题，因为n不包含在范围内，不应该添加到最终总数中。

理想情况下，您需要反转逻辑，并以范围相同的方式遍历它。

def func(start,end, step):
    if(start >= end):
        return 0

    return start + func(start + step, end, step)

Answer 3

你想要计算所有奇数整数的和从1到，但不包括，n。

这就留下了两种可能性：

1. 如果n是<= 1，则没有要和的数字，所以和是0。
2. 列表中可能包含的最高数字是n-1，但只有当它是奇数时才会包含。无论哪种方式，其余的和是“从1到n-1的所有奇数整数的和”(听起来很熟悉吗？)

这意味着：

def f1(n):
    if n <= 1:
        return 0
    else:
        isOdd = (n-1)%2==1
        return f1(n-1) + (n-1 if isOdd else 0)