How do I convert the recursive algorithm to iterative algorithm?

See more:

Javascript

Java

algorithm

I do not have much knowledge abt java.

I have code which is a recursive method. But when I am trying to convert it into Iterator method I am getting runtime error


package com.algo;

import java.util.ArrayList; 
import java.util.Scanner; 
import java.util.*; 
 
class inputIter 
{ 
    private static HashMap<integer,>> cachedSolutions; 
    public static void main(String[] args) 
    { 
        cachedSolutions = new HashMap<integer,>>(); 
        for (int j = 12; j < 13; ++j) 
        { 
            ArrayList<integer> answer = minLen(j); 
            Collections.sort(answer); 
            Collections.reverse(answer); 
            for (int i = 0; i < answer.size(); ++i) 
            { 
                if (i != 0) 
                    System.out.printf("+"); 
                System.out.printf("%d^2", answer.get(i)); 
            } 
            System.out.println(); 
        } 
    } 
 
    public static ArrayList<integer> minLen(int n) 
    {
    ArrayList<integer> guess = new ArrayList<integer>();
     
        // base case of recursion 
    while(n >0){ 
        // new base case: problem already solved once before 
        if (cachedSolutions.containsKey(n)) 
        { 
            // It is a bit tricky though, because we need to be careful! 
            // See how below that we are modifying the 'guess' array we get in? 
            // That means we would modify our previous solutions! No good! 
            // So here we need to return a copy 
            ArrayList<integer> ans = cachedSolutions.get(n); 
            ArrayList<integer> copy = new ArrayList<integer>(); 
            for (int i: ans) copy.add(i); 
            return copy; 
        } 
 
        ArrayList<integer> best = null; 
        int bestInt = -1; 
        // THIS IS WRONG, can you figure out why it doesn't work?: 
        // for (int i = 1; i*i <= n; ++i) 
        for (int i = (int)Math.sqrt(n); i >= 1; --i) 
        { 
            // Check what happens if we use i^2 as part of our representation
        n = n - (i*i); 
            guess = new ArrayList<integer>(); 
 
            // If we haven't selected a 'best' yet (best == null) 
            // or if our new guess is better than the current choice (guess.size() < 

best.size()) 
            // update our choice of best 
            if (best == null || guess.size() < best.size()) 
            { 
                best = guess; 
                bestInt = i; 
            } 
        } 
 
        best.add(bestInt); 
 
        // check... not needed unless you coded wrong 
        int sum = 0; 
        for (int i = 0; i < best.size(); ++i) 
        { 
            sum += best.get(i) * best.get(i); 
        } 
        if (sum != n) 
        { 
            throw new RuntimeException(String.format("n = %d, sum=%d, arr=%s\n", n, 

sum, best)); 
        } 
 
        // New step: Save the solution to the global cache 
        cachedSolutions.put(n, best); 
 
        // Same deal as before... if you don't return a copy, you end up modifying your 

previous solutions 
        //  
        ArrayList<integer> copy = new ArrayList<integer>(); 
        for (int i: best) copy.add(i); 
        return copy; 
    }
	return guess;} 
}

____________
Output:

Exception in thread "main" java.lang.RuntimeException: n = -2, sum=9, arr=[3]

at com.algo.inputIter.minLen(inputIter.java:77)
at com.algo.inputIter.main(inputIter.java:15)

___________________________________



package com.algo;

import java.util.ArrayList;
import java.util.Scanner;
import java.util.*;

class GetInputFromUser
{
    private static HashMap<integer,>> cachedSolutions;
    public static void main(String[] args)
    {
        cachedSolutions = new HashMap<integer,>>();
        for (int j = 12; j < 13; ++j)
        {
            ArrayList<integer> answer = minLen(j);
            Collections.sort(answer);
            Collections.reverse(answer);
            for (int i = 0; i < answer.size(); ++i)
            {
                if (i != 0)
                    System.out.printf("+");
                System.out.printf("%d^2", answer.get(i));
            }
            System.out.println();
        }
    }


    public static ArrayList<integer> minLen(int n)
    {
        // base case of recursion
        if (n == 0)
            return new ArrayList<integer>();

        // new base case: problem already solved once before
        if (cachedSolutions.containsKey(n))
        {
            // It is a bit tricky though, because we need to be careful!
            // See how below that we are modifying the 'guess' array we get in?
            // That means we would modify our previous solutions! No good!
            // So here we need to return a copy
            ArrayList<integer> ans = cachedSolutions.get(n);
            ArrayList<integer> copy = new ArrayList<integer>();
            for (int i: ans) copy.add(i);
            return copy;
        }

        ArrayList<integer> best = null;
        int bestInt = -1;
        // THIS IS WRONG, can you figure out why it doesn't work?:
        // for (int i = 1; i*i <= n; ++i)
        for (int i = (int)Math.sqrt(n); i >= 1; --i)
        {
            // Check what happens if we use i^2 as part of our representation
            ArrayList<integer> guess = minLen(n - i*i);

            // If we haven't selected a 'best' yet (best == null)
            // or if our new guess is better than the current choice (guess.size() < best.size())
            // update our choice of best
            if (best == null || guess.size() < best.size())
            {
                best = guess;
                bestInt = i;
            }
        }

        best.add(bestInt);

        // check... not needed unless you coded wrong
        int sum = 0;
        for (int i = 0; i < best.size(); ++i)
        {
            sum += best.get(i) * best.get(i);
        }
        if (sum != n)
        {
            throw new RuntimeException(String.format("n = %d, sum=%d, arr=%s\n", n, sum, best));
        }

        // New step: Save the solution to the global cache
        cachedSolutions.put(n, best);

        // Same deal as before... if you don't return a copy, you end up modifying your previous solutions
        // 
        ArrayList<integer> copy = new ArrayList<integer>();
        for (int i: best) copy.add(i);
        return copy;
    }
}

_______________


OUTPUT
2^2+2^2+2^2