递归(recurse)与迭代(iteration)

大家好，欢迎来到IT知识分享网。

1.概念

递归概念

递归，在数学与计算机科学中，是指在方法的定义中使用方法自身。也就是说，递归算法是一种直接或者间接调用自身方法的算法。简言之：在定义自身的同时又出现自身的直接或间接调用。
注意：递归必须要有一个退出的条件!

递归算法解决问题的特点：

在做递归算法的时候，一定要把握住出口，也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。其实这个出口是非常好理解的，就是一个条件，当满足了这个条件的时候我们就不再递归了。

迭代概念

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。

迭代和递归的关系和区别

2.实际问题

求n的阶乘

public class Demo6 { 
    public static void main(String[] args) { 
    System.out.println(fact(5)); } / * 求n的阶乘f1（n) 求n的阶乘--->fact（n-1）求n-1的阶乘 * 1.找重复(规模更小）；n*(n-1)的阶乘，求n-1的阶乘是原问题的重复（规模更小）——子问题 * 2.找变化；变化的量应作为参数 * 3.找边界；出口 */ public static int fact(int n) { 
    if(n == 1) { 
    return n = 1; }else { 
    return n*fact(n-1); } } } 

斐波那契数列

递归实现

int fib(int n){ 
    if(n>1) return fib(n-1) + fib(n-2); else return n; // n = 0, 1时给出recursion终止条件  } 

迭代实现

int fib(int n){ 
    int i, temp0, temp1, temp2; if(n<=1) return n; temp1 = 0; temp2 = 1; for(i = 2; i <= n; i++){ 
    temp0 = temp1 + temp2; temp2 = temp1; temp1 = temp0; } return temp0; } 

3.自己遇到的问题

/ * @author Kino * @create 2022-10-20 20:23 */ public class Test { 
    public static void main(String[] args) { 
    double digui = digui(5, 1, 1, 1); // double digui = digui1(5, 1, 1, 1); System.out.println(digui); } public static double digui(int level,double r1,double r2, double r3){ 
    if (level == 1){ 
    return r1 + r2 + r3; } else { 
    double sum = r1 + r2 + (r3 * digui(level-1,r1,r2,r3)) / (r3 + digui(level-1,r1,r2,r3)); return sum; } }; public static double digui1(int level,double r1,double r2, double r3){ 
    if (level == 1){ 
    return r1 + r2 + r3; } else { 
    return r1 + r2 + (r3 * digui1(--level,r1,r2,r3)) / (r3 + digui1(--level,r1,r2,r3)); } }; } 

当运行digui1方法的时候就会报出StackOverflowError错误。而修改后的digui方法就可以正常运行。在运行digui1方法的debugger的过程中发现，level1的时候递归并没有停止，而是继续往下走了，下一个就是level0。

4.解决方法