嗨,有谁能帮我理解这段代码中发生了什么？

Question

我知道这是一个递归函数,它返回表示数字的方式的数量,n作为不大于数字的总和k,按顺序,但我无法理解它是如何完成的.

def all_sums(n, k):

    if n == 0:
        return 1
    elif n < 0: 
        return 0
    else:
        res = 0
        for i in range(1, k+1):
            res = res + all_sums(n-i, k)
        return res

Answer 1

首先,您应该知道此函数是递归的.基本上这意味着代码调用自身,具有不同的数字.递归的一个很好的例子是fibbonacci序列,它将序列中的前两个数字加在一起以得到下一个数字.代码是:

def F(n):
    if n == 0:
        return 0 #base case no.1 because there are no previous elements to add together.
    elif n == 1:
        return 1 #base case no.2 because there are not enough previous elements to add together.
    else:
        return F(n-1)+F(n-2) #adds together the result of whatever the last number in the sequence was to whatever the number before that was.

一旦了解了递归的工作原理,您就可以直接浏览代码.如果这在精神上很难做到,请尝试在一张纸上画出来.我发现在编程任何东西时,这通常是一个有用的策略.出于这个原因,我总是在电脑附近放一张纸和一支铅笔.让我们一起快速破解代码,只是为了了解正在发生的事情:

def all_sums(n,k):

在这里,我们定义方法,并传递给参数,n以及k它.

if n == 0:
    return 1

这是递归函数的"基本情况",主要是为了确保代码不会永远运行,并关闭函数.

elif n < 0:
    return 0

这表明如果n小于0,则返回0(因为n不能为负).这被认为是一个"特殊情况",以防止有人意外搞砸程序.

else:
    res = 0

如果没有其他"特殊情况"发生,请执行以下所有操作.首先,我们设置一个等于0的变量.

for i in range(1, k+1):
    res = res + all_sums(n-i, k)

调用从1开始的for循环并遍历每个整数(但不包括)k+1.对于每次迭代,它将我们的res变量设置res为以前的任何内容加上调用相同函数的结果,使用n-i第一个变量.

return res

在for循环完成后,此代码只输出res的结果.

如果要查看代码的工作方式,请将print语句添加到代码的各个部分并查看其输出内容.此外,如果这让您感到困惑,您可能想要稍微阅读一下递归.

编辑

这是all_sums(3,3)使用伪代码的基本操作.首先,这里是你的代码添加了一些注释和打印语句(这是我在名为"test.py"的文件中运行的代码:

def all_sums(n, k):

    if n == 0: #base case 1
        return 1
    elif n < 0: #base case 2
        return 0
    else: #recursive case
        res = 0
        for i in range(1, k+1):
            res = res + all_sums(n-i, k)
        print res #output res to the screen
        return res

print all_sums(3,3)

这是我对代码的追踪.请注意,每次进入某个级别时,由于变量的范围,res是一个不同的变量.每次我进入选项卡时,都是在我正在运行新函数调用内部的代码时.

all_sums(3,3):
    res = 0
    0 + all_sums((3-1),3)
        res = 0
        0 + all_sums((2-1),3)
            res = 0
            0 + all_sums((1-1),3)
                returning 1 #first base case
            1 + all_sums((1-2),3)
                returning 0 #second base case
            1 + all_sums((1-3),3)
                returning 0 #second base case
            PRINTING 1 TO THE SCREEN
            returning 1 #end of recursive case
        1 + all_sums((2-2),3)
            returning 1 #first base case
        2 + all_sums((2-3),3)
            returning 0 #second base case
        PRINTING 2 TO THE SCREEN
        returning 2 #end of recursive case
    2 + all_sums((3-2),3)
        res = 0
        0 + all_sums((1-1),3)
            returning 1 #first base case
        1 + all_sums((1-2),3)
            returning 0 #second base case
        1 + all_sums((1-3),3)
            returning 0 #second base case
        PRINTING 1 TO THE SCREEN
        returning 1 #end of recursive case
    3 + all_sums((3-3),3)
        returning 1 #first base case
    PRINTING 4 TO THE SCREEN
    returning 4 #end of recursive
returning 4 #end of recursive case (and your original function call)

PRINTING 4 TO THE SCREEN AS THE RESULT OF all_sums(3,3)