【数据结构与算法】递归Recursion的介绍和基本使用

1. 递归的概念

递归就是方法自己调用自己，每次调用时传入不同的变量。递归有助于编程者解决复杂的问题，同时可以让代码变得简洁

程序调用自身的编程技巧称为递归(recursion)。递归作为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进，当边界条件满足时，递归返回

2. 递归的应用场景

• 各种数学问题：8皇后问题、汉诺塔、阶乘问题、迷宫问题(回溯)、球和篮子的问题(google编程大赛)
• 各种算法中也会使用到递归：快排、归并排序，二分查找、分治算法等

3. 递归的调用机制

我们通过阶乘问题，来简单的看下递归的调用机制

public class FactorialTest {

    public static void main(String[] args) {

        System.out.println(factorial(5));

    }

    public static int factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return factorial(n - 1) * n;
        }
    }

}

运行程序，结果如下：

120

4. 递归需要遵守的重要规则

• 执行一个方法时，就创建一个新的受保护的独立空间(栈空间)
• 方法的局部变量是独立的，不会相互影响, 比如阶乘的n变量
• 如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据
• 递归必须向退出递归的条件逼近，否则就是无限递归，出现StackOverflowError异常
• 当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕