java - 试图理解递归

Question

public static int fun(int x) {
    if(x<1){
        return 1;
    } else {

        return x+fun(x-1)+fun(x-2);
    }
}

我在尝试解决给定数字的递归时遇到了一些问题。例如x可能是 3 或 4 什么的，结果会是什么。

Answer 1

试试这个来帮助你理解：

//do first call with trace ""
public static int fun(int x, String trace) {
    System.out.println(trace + " ENTRY x=" + x);
    int ret;
    if(x<1){
        ret = 1;
    } else {   
        ret = x+fun(x-1, trace+'<')+fun(x-2, trace+'>');
    }
    System.out.println(trace + " RETURN " + ret);
    return ret;
}

Answer 2

当您调用 x = 3 的函数时，您会得到如下所示的递归调用：

fun(3) -> 3 + fun(2) + fun(1){1} fun(2) -> 2 + fun(1){2} + fun(0){1}

乐趣(1){2} -> 1 + 乐趣(0){2} + 乐趣(-1) 乐趣(0){2} -> 1 乐趣(-1) -> 1

它回滚到 fun(1){2} -> 1 + 1 + 1 -> 3

如此有趣(2) -> 2 + 3 + fun(0){1} fun(0){1} -> 1 因此，有趣(2) -> 2 + 3 + 1 -> 6

然后调用 fun(1){1}，执行与 fun(1){1} 相同的过程。

这一切都回滚到 fun(3) -> 3 + 6 + 3 -> 12

Answer 3

x=3
return 3+fun(2)+fun(1)         // so return 3+6+3
    fun(2) = 2+fun(1)+fun(0)   // so fun(2)=6
        fun(1) = 1+fun(0)+1
            fun(0) = 1
        fun(0) = 1

    fun(1) = 1+fun(0)+1        // so fun(1)=3
         fun(0) = 1

result return 12