如何理解这种递归算法

Question

def sum(a):
    if a==1:
        s=1
    else:
        s=1+2*sum(a-1)
    return s

函数:计算数列之和。它的公共比率是2，最后一项是2^( a-1)，第一项是1。

为什么它使用s=1+2*sum(a-1)来实现这个函数？

Answer 1

def sum1(a):
    if a==1:
        s=1
    else:
        s=1+2*sum1(a-1)
    return s

这个函数是做什么的，让我们以a=4为例。

(1) s = 1 + 2*sum1(4-1) = 1 + 2*sum1(3) = 1 + 2*s2

(2) s2 = 1 + 2*sum1(3-1) = 1 + 2*sum1(2) = 1 + 2*s3

(3) s3 = 1 + 2*sum(2-1) = 1 + 2*sum(1) = 1 + 2*s4 = 1+2 = 3

Going BackWard : (3 * 2 + 1 ) * 2 + 1 = (7) * 2 + 1 = 15

对于更大的数字，您会注意到这是2^a - 1的公式。

打印和 2^a - 1

Difference: (4, 3)
Difference: (8, 7)
Difference: (16, 15)
Difference: (32, 31)
Difference: (64, 63)
Difference: (128, 127)
Difference: (256, 255)

Answer 2

@忠义:我把这个问题理解为“递归是如何工作的”。

递归存在于Python中，但我发现要解释它在Python中的工作方式有点困难。相反，我将展示在球拍 (一个Lisp )中是如何工作的。

首先，我将把上面提供的yoursum重写为mysum

def yoursum(a):
    if a==1:
        s=1
    else:
        s=1+2*yoursum(a-1)
    return s


def mysum(a):
    if a == 1:
        return 1
    return 1 + (2 * mysum(a - 1))

for i in range(1, 11):
    print(mysum(i), yoursum(i))

它们在功能上是相同的：

# Output
1 1
3 3
7 7
15 15
31 31
63 63
127 127
255 255
511 511
1023 1023

在球拍中，mysum看起来是这样的：

#lang racket

(define (mysum a)
  (cond
    ((eqv? a 1) 1)
    (else (+ 1 (* 2 (mysum (sub1 a)))))))

但是，我们可以使用称为拟引用和取消引用的语言特性来显示递归所做的事情：

#lang racket

(define (mysum a)
  (cond
    ((eqv? a 1) 1)
    (else `(+ 1 (* 2 ,(mysum (sub1 a))))))) ; Notice the ` and ,

以下是这对几个产出的作用：

> (mysum 1)
1
> (mysum 2)
'(+ 1 (* 2 1))
> (mysum 3)
'(+ 1 (* 2 (+ 1 (* 2 1))))
> (mysum 4)
'(+ 1 (* 2 (+ 1 (* 2 (+ 1 (* 2 1))))))
> (mysum 5)
'(+ 1 (* 2 (+ 1 (* 2 (+ 1 (* 2 (+ 1 (* 2 1))))))))

可以将递归步骤视为替换表达式(1 + 2 * rest-of-the-computation)。

请评论或要求澄清，如果有部分仍然没有意义。

Answer 3

公式解释

1+2*(sumOf(n-1))

这不是几何级数的通用公式。这个公式只适用于比率为2，第一项为1的情况，因此它是如何工作的。

具有第一项=1和r=2的几何级数是

1,2,4,6,8,16,32,64

事实1

这里可以清楚地看到，第n项总是等于sumOf(n-1)项+ 1 ，让声明一个来自事实1的方程。

n = sumOf(n-1) + 1 =======> Eq1.

Let put our equation to test

    put n = 2 in Eq1
    2 = sumOf(2-1) + 1

we know that sumOf(1) is 1 then 
2 = 2 ==> proved

所以如果n= sumOf(n-1)+1那么事实2

N项的和是n项+和(n-1)项，允许从事实2声明方程。

sumOf(n) = sumOf(n-1) + n ==> eq2

让我们把eq1放在eq2中，即n= sumOf(n-1) + 1

sumOf(n) = sumOf(n-1) + sumOf(n-1) + 1 ==> eq3

化简

sumOf(n) = 2 * sumOf(n-1) + 1

重排

sumOf(n) = 1 + 2 * sumOf(n-1) ==> final Equation

现在编码这个方程

我们知道sumOf第一学期总是1，所以，这是我们的基本情况。

    def sumOf(a):
        if a==1:
            return 1

所以现在，第一个n项的和将是1 + 2 * sumOf(n-1)，==>，从最终方程

把这个方程放在另一部分

    def sumOf(a):
        if a==1:
            return 1
        else:
            return 1 + 2 * sumOf(a-1)