java - 再帰を理解しようとする

Question

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

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

特定の数値についてこの再帰を解決しようとすると、いくつかの問題が発生します。たとえば、x3 か 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

そう fun(2) -> 2 + 3 + fun(0){1} fun(0){1} -> 1 したがって、 fun(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