Keep multiplying found values in an array error with recursion-CodePudding

I struggle with this coding "challenge". I need to look for the original value in nums. If its there, multiply by two and redo the whole thing. Return the value if there is no more same value.

It works on a lot of test cases but I get a weird error with this set while debugging. After I iterate the array and was ready to return the right value, instead of returning the 16, it calls the findFinalValue again and iterates itself from 16 down again to 4.

public class Main {

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {8,19,4,2,15,3};
        System.out.println(s.findFinalValue(nums, 2));

    }

}

class Solution {
    public int findFinalValue(int[] nums, int original) {
        
        for(int n: nums){
            if(n == original){
                original*=2;
                findFinalValue(nums, original);
            }
            
        }
        return original;
    }
}

CodePudding user response：

Guessing that your problem is that your are not implemented recursion properly:

class Solution {
    public int findFinalValue(int[] nums, int original) {
        int found = original;
        for(int n: nums){
            if(n == original){
                found = findFinalValue(nums, found * 2);
            }
            
        }
        return found;
    }
}

CodePudding user response：

It is not iterating from 16 to 4, it is how recursion works. You need to pass the result back or store it in a global variable. Once the dead-end is achieved in recursion it backtracks and comes back to its original state.

Solution

class Solution {
    public int findFinalValue(int[] nums, int original) {
        int isPresent = false;
        for(int n: nums){
            if(n == original){
                isPresent = true;
                break;
            }
        }
        if(isPresent) {
           original = findFinalValue(nums, original*2);
        }
        return original;
    }
}

Frankly speaking, you can optimize it by sorting the array at first and then using binary search for finding elements, in addition, the array passed in the next state can be reduced till the index has read. Because original has become twice

CodePudding user response：

I wouldn't use recursion, but since I think you're asking about a recursive solution, I would do it like this:

public int findFinalValue(int[] nums, int original) {
    return IntStream.of(nums).anyMatch(n -> n == original)
           ? findFinalValue(nums, 2 * original)
           : original;
}