If I divide a recursive call by another, would I get an infinite loop?

user_9023057 0
Viewed 139

I'm experimenting with recursion in Java and I have this method:

public static int recursion(int n) {
    if(n==1) {
        return 2;
    } else {
        int test = (recursion(n-1))/(recursion(n-1));
        return test;
    }
}

If I run it with n = 50, it never prints anything, so I'm guessing the recursive calls are infinite? Could anybody explain why?

recursion java
2 Answers

It is not infinite, just huge. You will do roughly 2^50 recursive calls. Even if each call takes just one nanosecond (which is much too low) this means a total run time of about two weeks.

user_17965790

Here, recursion() is called like a binary tree

recursion(50) -> recursion(49) -> recursion(48) ...
                                  recursion(48) ...
                 recursion(49) -> recursion(48) ...
                                  recursion(48) ...

So the binary tree height is 49.
Then recursion() is called: total number of nodes of the tree times. This equates to 2^(h+1)-1 = 2^(49+1)-1 = 2^(50)-1 times.
That's huge, which takes a very long time to execute. This is the problem, but it's not infinite.

You can instead do the following, which is not a problem because recursion(n) to recursion(n-1) is called only once:

public static int recursion(int n) {
    if(n==1) {
        return 2;
    } else {
        int test = recursion(n-1);
        test = test/test
        return test;
    }
}
user_42073060
Related