[CSE Help] Improve this algorithm?

[LoudPacks]

Assignment:

 

Current Code:

public class Main {


	public static int RecursiveFirst(int n) throws IllegalArgumentException {
		if (n <= 0) {
			throw new IllegalArgumentException();
		} else if (n == 1) {
			return 1;
		} else if ((n % 2) == 0) {
			return 1 + RecursiveFirst(n / 2);
		} else {
			return 1 + RecursiveFirst(n - 1);
		}

	}

	public static void main(String Args[]) {
		int r = 0;
		for (int i = 1; i < 100; i++) {
			r = RecursiveFirst(i);
			System.out.println(r);
		}
	}

}

I have 0 idea on how to improve the run time of the algorithm so if anyone has ideas that would be nice.

 

Edit: what I came up with:

public static int RecursiveFirst(int n) throws IllegalArgumentException {
		ArrayList<Integer> res = new ArrayList<Integer>();
		res.add(n);
		while (n != 1) {
			if (n == 0) {
				throw new IllegalArgumentException();
			} else if (n % 2 == 0) {
				n = 1 + (n / 2);
				res.add(n);
			} else {
				n = 1 + (n - 1);
				res.add(n);
			}
			n /= 2;
		}
		return res.size();

	}

	public static void main(String Args[]) {
		for (int i = 1; i <= 10000; i++) {
			System.out.println(RecursiveFirst(i));
		}
	}

Edited September 29, 2016 by LoudPacks

[Token]

	public static int rec1(int n) {
		c1++;
		if (n == 1) {
			return 1;
		} else if (n % 2 != 0) {
			return 1 + rec1(n - 1);
		} else {
			return 1 + rec1(n / 2);
		}
	}

	static int c2 = 0;

	public static int rec2(int n) {
		c2++;
		if (n == 1) {
			return 1;
		} else if (n % 2 != 0) {
			return 1 + rec2(n - 1);
		} else {
			int sum = 0;
			do {
				n = n / 2;
				sum++;
			} while (n % 2 == 0);
			if (n == 1)
				return 1 + sum;
			return 1 + sum + rec2(n - 1);
		}
	}

	public static void main(String[] args) {
		System.out.println(rec1(3128) + "; iterations: " + c1);
		System.out.println(rec2(3128) + "; iterations: " + c2);
	}

Output:

16; iterations: 16
16; iterations: 5

If you studied CPU architecture you should know every function call creates a new stackframe and new local variables with each call, taking up a lot of memory. 

 

SP = stack pointer register

BP = base pointer register

 

They are in your CPU, BP points to the base of the stack and SP points to the top stackframe aka the function call being executed by the CPU at a given moment.

Recursion is very inefficient memory-wise so the second function, which is still recursive but has an iterative component for powers of 2, is obviously superior.

[Solzhenitsyn]

What if you save the return value of each recursive call in a map, and then check to see if that value has been called previously at the start of each call? 

 

Edit:

 

Edited October 2, 2016 by Solzhenitsyn

[FrostBug]

try replacing

n % 2 == 0

with

(n & 1) == 0

From what I understand, modulo is a fairly expensive operation.

Tho I reckon jabba mite optimize it by itself..

[Ericthecmh]

	public static int rec1(int n) {
		c1++;
		if (n == 1) {
			return 1;
		} else if (n % 2 != 0) {
			return 1 + rec1(n - 1);
		} else {
			return 1 + rec1(n / 2);
		}
	}

	static int c2 = 0;

	public static int rec2(int n) {
		c2++;
		if (n == 1) {
			return 1;
		} else if (n % 2 != 0) {
			return 1 + rec2(n - 1);
		} else {
			int sum = 0;
			do {
				n = n / 2;
				sum++;
			} while (n % 2 == 0);
			if (n == 1)
				return 1 + sum;
			return 1 + sum + rec2(n - 1);
		}
	}

	public static void main(String[] args) {
		System.out.println(rec1(3128) + "; iterations: " + c1);
		System.out.println(rec2(3128) + "; iterations: " + c2);
	}

Output:

16; iterations: 16
16; iterations: 5

If you studied CPU architecture you should know every function call creates a new stackframe and new local variables with each call, taking up a lot of memory. 

 

SP = stack pointer register

BP = base pointer register

 

They are in your CPU, BP points to the base of the stack and SP points to the top stackframe aka the function call being executed by the CPU at a given moment.

Recursion is very inefficient memory-wise so the second function, which is still recursive but has an iterative component for powers of 2, is obviously superior.

 

 

Go with the second solution first, then do the first one if necessary.

 

Although Token is right, this is like trying to make a gun shot wound better by putting a bandage on it. It may save some runtime but the real improvement is the solution below.

 

Optimizing from a recusive to an iterative approach will probably cut your runtime by several times, but using the below solution can cut your runtime by an entire order of magnitude or more (ie. from n^2 to n).

 

You should be caching the results of previously computed answers and using it from cache (called Dynamic programming), which is what Solzhenitsyn is suggesting.

 

What if you save the return value of each recursive call in a map, and then check to see if that value has been called previously at the start of each call? 

 

Edit:

 

try replacing

n % 2 == 0

with

(n & 1) == 0

From what I understand, modulo is a fairly expensive operation.

Tho I reckon jabba mite optimize it by itself..

Pretty sure it does. Tried it out before and I think the runtime's about the same

Edited October 2, 2016 by Ericthecmh

[Botre]

Recursion is very inefficient memory-wise

The cost  of recursion is language/  compiler-dependent and it can actually be done extremely efficiently (albeit not so much in java).

 

https://en.wikipedia.org/wiki/Tail_call