递归中的return

发表于 分类于

　　递归中的return常用来作为递归终止的条件，但是对于返回数值的情况，要搞明白它是怎么返回的。递归的方式就是自己调用自己，而在有返回值的函数中，上一层的函数还没执行完就调用下一层，因此，当达到递归终止条件时，首先return的是最底层调用的函数，return之后，继续执行上一层调用该函数之后的代码，此时我们看到的是上一层的情况，当上一层剩余的代码执行完之后，表示上一层的函数也结束，此时再返回上上一层，执行递归代码之后的代码，如此往复循环，直到返回到最上层，结束整个递归过程。需要注意的是，上一层执行递归之后的代码的时候，会调用下一层返回的值，也可以理解为在执行上一层代码的时候会调用下一层的实现过程，直到下一层执行完返回一个数值，然后再加上上一层的数值，就构成了上一层return的东西，如此往复。下面介绍例子。

1
2
3
4
5
6
static int Sum(int n)
        {
            if (n <= 1)                  //#1
                return n;                //#2
            return n+Sum(n - 1);         //#3
        }

　　上面是一个递归求和的代码，例如我们传参100进去，第一次执行到#3位置的时候，调用Sum(99)，此时Sum(100)还没有执行完，就已经开始执行Sum(99)了，Sum(100)要等待Sum(99)执行完后才开始执行自己未执行完的程序。同理当Sum(99)执行到#3位置的时候，也会调用Sum(98)，此时Sum(99)还没有执行完，Sum(99)要等到Sum(98)执行完之后才开始执行自己未执行完的程序…..就这样一直循环到n=1的时候，也就是在执行Sum(1)的时候满足递归结束条件，即return 1;这个时候表示Sum(1)已经执行完毕，接下来要执行Sum(2)中未执行完的内容，也就是return 2+Sum(1);而Sum(1)已经返回1，因此Sum(2)返回2+1=3，Sum(2)执行完毕，开始执行Sum(3)未执行完的内容…..如此往复，一直到Sum(99)执行完毕后，再执行Sum(100)中未执行完的内容，也就是return 100+Sum(99),而Sum(99)已经执行完毕，有返回值，因此Sum(100)=100+Sum(99)=5050。至此，整个递归过程结束，返回累加值。