递归_递归都是用栈吗

递归

1、递归的定义

我们把一个直接调用自己或通过一系列的调用语句间接的调用自己的函数，称作递归函数

2、递归满足两个条件

• 有反复执行的过程（调用自身）
• 有跳出反复执行过程的条件（递归出口）

3、递归的过程

• 递归其实就是压栈和出栈的过程
• 他会把这个函数的所有信息全部压入栈中
• 然后每次从栈顶把信息拿出来，进行还原，重构，变成当前需要的返回值
• 所谓的递归函数就是调用系统栈的过程，一个函数调用子函数之前，会把所有的信息全部压入栈中，信息完全保存，子过程返回之后会把这些信息进行彻底的还原
• 理论上，任何递归行为都可以改成非递归

4、几个递归算法的例子

例子一：

求下面函数输出的值

public class Test {

    public static void main(String[] args) {
        test(4);
        test1(4);
    }

    public static void test(int n){
        if (n > 2) {
            test(n - 1);
        }
        System.out.println(n);
    }

    public static void test1(int n ){
        if (n > 2){
            test1(n - 1);
        } else {
            System.out.println(n);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

test()函数输出的值是： 2 3 4

如图所示

栈是先进后出，所以这里先压栈 4 3 2

所以出栈的顺序也应该是2 3 4

test1()函数的值应该是 2

原因：只有当最后一次出栈的时候才是else所以应该是2

例子二

斐波那契数：请使用递归的方式，求出斐波那契数1,1,2,3,5,8,13…给你一个整数n，求出它的斐波那契数是多少？

解题思路：

​ n = 1 1 ;n=2 1;n=3 f(n-1)+f(n-2)

​ 递归出口为当n==1或n==2的时候，返回1

public class Test1 {

    public static void main(String[] args) {
        System.out.println(test(5));
    }

    public static int test(int n){
        if (n == 1 || n == 2){
            return 1;
        } else {
            return test(n-1) + test(n-2);
        }
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

例子三

有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个！以后每天猴子都吃其中的一半，然后再多吃一个。当到第十天时，想再吃时（还没吃），发现只有1个桃子了。问题：最初共多少个桃子？

思路分析：

day10 1
day9 (1+1)*2 ==> (f(day10)+1)*2 ==> (f(day9 + 1)+1)*2 所以可以推导出(f(dayn + 1)+1)*2

总结：针对这种情况，一般从已知推未知，从未知推已知（无法找到递归出口）

public class Test2 {

    public static void main(String[] args) {
        System.out.println(test(1));
    }

    public static int test(int day) {
        if (day == 10) {
            return 1;
        } else {
            return (test(day + 1) + 1) * 2;
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5、总结

1. 程序执行一个函数时，就创建一个新的受保护的独立空间(新函数栈)

2. 函数的局部变量是独立的，不会相互影响

3. 递归必须向退出递归的条件逼近，否则就是无限递归，死龟了:)

4. 当一个函数执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁。