## Code optimization techniques

### Code optimization techniques

May I have some of the techniques used frequently to optimize a program i.e. to decrease time taken to get an answer?

For example, building a list is often better than branched recursion(at least I think this one is correct, but I'm not sure)

For example, building a list is often better than branched recursion(at least I think this one is correct, but I'm not sure)

Math and Programming are complements

### Re: Code optimization techniques

See TopCoder tutorials and other more general Google searches. Research dynamic programming, memoization, and sieving.

- kenbrooker
**Posts:**129**Joined:**Mon Feb 19, 2018 3:05 am**Location:**Oregon, USA

### Re: Code optimization techniques

Trying to learn more about Dynamic Programming vs Recursion and about Tabulation vs Memoization, particularly the latter, as aided by Geeks for Geeks (which I highly recommend for beginner-intermediates like me).

Geeks for Geeks presents an application of Memoization to computing the "n"th Fibonacci number, by recursively referencing a so-called "lookup" table/array.

I will enter their/my code below but to get right to my question -- I've printed out a statement for each call to the recursive function and a listing of the lookup array going into that call, as follows, and I just don't understand --

Why does lookup[2] become 1 from the prior fib(0) call?

Maybe because I turn 7

fib(5) called with: ***************************** 9 calls total vs 15 for Top-Down Recursion w/o lookup *******************

[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(4) called with:

[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(3) called with:

[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(2) called with:

[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(1) called with:

[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(0) called with:

[-1, 1, -1, -1, -1, -1, -1, -1, -1, -1] first change, via prior fib(1) and if(n <= 1) lookup[n] = n so lookup[1] = 1

fib(1) called with:

[0, 1, 1, -1, -1, -1, -1, -1, -1, -1] via prior fib(0) and if(n <= 1) lookup[0] = 0 BUT lookup[2] = 1 also??

fib(2) called with:

[0, 1, 1, 2, -1, -1, -1, -1, -1, -1] via prior fib(1)

fib(3) called with:

[0, 1, 1, 2, 3, -1, -1, -1, -1, -1] via prior fib(2)

Fibonacci(5) = 5

Geeks for Geeks presents an application of Memoization to computing the "n"th Fibonacci number, by recursively referencing a so-called "lookup" table/array.

I will enter their/my code below but to get right to my question -- I've printed out a statement for each call to the recursive function and a listing of the lookup array going into that call, as follows, and I just don't understand --

Why does lookup[2] become 1 from the prior fib(0) call?

Maybe because I turn 7

**1**tomorrow?fib(5) called with: ***************************** 9 calls total vs 15 for Top-Down Recursion w/o lookup *******************

[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(4) called with:

[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(3) called with:

[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(2) called with:

[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(1) called with:

[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(0) called with:

[-1, 1, -1, -1, -1, -1, -1, -1, -1, -1] first change, via prior fib(1) and if(n <= 1) lookup[n] = n so lookup[1] = 1

fib(1) called with:

[0, 1, 1, -1, -1, -1, -1, -1, -1, -1] via prior fib(0) and if(n <= 1) lookup[0] = 0 BUT lookup[2] = 1 also??

fib(2) called with:

[0, 1, 1, 2, -1, -1, -1, -1, -1, -1] via prior fib(1)

fib(3) called with:

[0, 1, 1, 2, 3, -1, -1, -1, -1, -1] via prior fib(2)

Fibonacci(5) = 5

Code: Select all

```
/*
a) Memoization (Top Down):
The memoized program for a problem is similar to the recursive version with
a small modification that it looks into a lookup table before computing solutions.
We initialize a lookup array with all initial values as NIL.
Whenever we need the solution to a subproblem, we first look into the lookup table.
If the precomputed value is there then we return that value, otherwise,
we calculate the value and put the result in the lookup table so that it can be reused later.
Following is the memoized version for nth Fibonacci Number.
// Java program for Memoized version
public class Fibonacci
{
final int MAX = 100;
final int NIL = -1;
int lookup[] = new int[MAX];
// Function to initialize NIL values in lookup table
void _initialize()
{
for (int i = 0; i < MAX; i++)
lookup[i] = NIL;
}
// function for nth Fibonacci number
int fib(int n)
{
if (lookup[n] == NIL) //Recursion Function but How can lookup[] even be referenced?! Via f._initialize()?
{
if (n <= 1)
lookup[n] = n;
else
lookup[n] = fib(n-1) + fib(n-2);
}
return lookup[n];
}
public static void main(String[] args)
{
Fibonacci f = new Fibonacci();
int n = 9;
f._initialize();
System.out.println("Fibonacci number is" + " " + f.fib(n));
}
}
// This Code is Contributed by Saket Kumar
Both Tabulated and Memoized store the solutions of subproblems.
In Memoized version, table is filled on demand while in Tabulated version,
starting from the first entry, all entries are filled one by one.
Unlike the Tabulated version, all entries of the lookup table are not necessarily filled in Memoized version.
For example, Memoized solution of the LCS problem doesn’t necessarily fill all entries.
--------------------------------------------------------------------------------------------------------------------
OUTPUT from my slightly modified code which is below:
fib(5) called with:
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(4) called with:
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(3) called with:
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(2) called with:
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(1) called with: *********9 calls vs 15 for Top-Down Recursion w/o lookup*********
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(0) called with:
[-1, 1, -1, -1, -1, -1, -1, -1, -1, -1] first change, via prior fib(1) and if(n <= 1) lookup[n] = n so lookup[1] = 1
fib(1) called with:
[0, 1, 1, -1, -1, -1, -1, -1, -1, -1] via prior fib(0) and if(n <= 1) lookup[0] = 0 BUT lookup[2] = 1 also??
******************
fib(2) called with:
[0, 1, 1, 2, -1, -1, -1, -1, -1, -1] via prior fib(1)
fib(3) called with:
[0, 1, 1, 2, 3, -1, -1, -1, -1, -1] via prior fib(2)
Fibonacci(5) = 5
--------------------------------------------------------------------------------------------------------------------
*/
import java.util.Arrays;
class GeekFibonacciMemoization //w/o public... and apparently unnecessary
{
int MAX = 10; //w/o final... and apparently unnecessary
int NIL = -1; //w/o final... and apparently unnecessary
int lookup[] = new int[MAX];
// Function to initialize NIL values in lookup table
void _initialize()
{
for (int i = 0; i < MAX; i++)
lookup[i] = NIL;
}
// Function for nth Fibonacci number
int fib(int n)
{
System.out.println(" fib(" +n+ ") called with:");
System.out.println(Arrays.toString(lookup));
System.out.println();
if (lookup[n] == NIL)
{
if (n <= 1)
lookup[n] = n;
else
lookup[n] = fib(n-1) + fib(n-2);
}
return lookup[n];
}
public static void main(String[] args)
{
GeekFibonacciMemoization f = new GeekFibonacciMemoization();
System.out.println();
int n = 5;
f._initialize();
System.out.println("Fibonacci(" +n+ ") = " + " " + f.fib(n));
}
}
```

Last edited by kenbrooker on Mon Dec 31, 2018 3:09 pm, edited 1 time in total.

"

*Good Judgment comes from Experience;*

Experience comes from Bad Judgment..."Experience comes from Bad Judgment

### Re: Code optimization techniques

It isn't set in the prior fib(0) call, it's set in the prior fib(2) call,kenbrooker wrote: ↑Sat Dec 29, 2018 10:22 pmWhy does lookup[2] become 1 from the prior fib(0) call?

*but this call has only completed after the fib(0) which it called has completed*. The second call to fib(1), where lookup[2] first appears as 1, is part of calculating fib(3), which happens after we have finished the first call to fib(2) and set lookup[2] to 1.

It might help when testing things like this to have a "depth" parameter in a recursion which you increment with each call. And then, for example, use the depth to add a number of spaces/tabs before each line when outputting it, to get a better idea of where you are. I

*think*it would look something like this, with the general flow of the program being to go in as "deep" as it can, then back up to the function which called it and then down to the next thing:

Code: Select all

```
fib(5) called with: [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(4) called with: [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(3) called with: [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(2) called with: [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(1) called with: [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(0) called with: [-1, 1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(1) called with: [0, 1, 1, -1, -1, -1, -1, -1, -1, -1] // *****
fib(2) called with: [0, 1, 1, 2, -1, -1, -1, -1, -1, -1]
fib(3) called with: [0, 1, 1, 2, 3, -1, -1, -1, -1, -1]
```

- kenbrooker
**Posts:**129**Joined:**Mon Feb 19, 2018 3:05 am**Location:**Oregon, USA

### Re: Code optimization techniques

Thanks for a Fine

Birthday Gift

I definitely get lost in recursion and I like your "depth" idea, anything to help me follow the fatal, to me, complication that you describe as

I think my key problem is concerning the Stack, specifically relating to "return" statements, and

I hope you will bear further with me for a very different approach.

For this fairly simple recursive code with the same

Preorder Straight "Tree" as my Fibonacci code:

Birthday Gift

**MHealy**...I definitely get lost in recursion and I like your "depth" idea, anything to help me follow the fatal, to me, complication that you describe as

*"then back up to the function which called it and then down to the next thing."*I think my key problem is concerning the Stack, specifically relating to "return" statements, and

I hope you will bear further with me for a very different approach.

For this fairly simple recursive code with the same

Preorder Straight "Tree" as my Fibonacci code:

Code: Select all

```
import java.util.Arrays;
class GeekRecursionMemoryProc
{
void printFun(int test)
{
System.out.println(" printFun(" +test+ "):");
if (test < 1)
return; // statement 0
else
{
System.out.println(" test1 = " +test); // statement 1
printFun(test-1); // statement 2
System.out.println(" test3 = " +test); // statement 3
return; // statement 4
}
}
}
class GeekRecursionMemory
{
public static void main(String args [ ])
{
double start = System.currentTimeMillis();
System.out.println();
GeekRecursionMemoryProc F = new GeekRecursionMemoryProc();
F.printFun(3);
System.out.println();
double finish = System.currentTimeMillis();
System.out.println("RunTime = " + (finish - start)/1000 + " Secs");
}
}
```

**The "back ups and then downs" make sense to me as follows**

with regard to the Stack --with regard to the Stack --

test1 = 3 3 test1 = 2 / test1 = 1 2 PreOrder "Tree" (test = 0) / 3 2 1 0 1 2 3 test3 = 1 1 test3 = 2 / test3 = 3 0 RunTime = 0.0 Secs CALLED Printed *********** ********* printFun(3): local test initialized to 3 and statements 4 to 0 pushed on stack and 0 false and test1 = 3 test1 = 3 printed by statement 1 and printFun(2) called by statement 2 printFun(2): local test initialized to 2 and statements 4 to 0 pushed on stack and 0 false and test1 = 2 test1 = 2 printed by statement 1 and printFun(1) called by statement 2 printFun(1): local test initialized to 1 and statements 4 to 0 pushed on stack and 0 false and test1 = 1 test1 = 1 printed by statement 1 and printFun(0) called by statement 2 (test = 0) printFun(0): local test initialized to 0 and statement 0 reads if(0 < 1) return to... printFun(1): finding printFun(1) statement 3 at top of stack test3 = 1 test3 = 1 printed by statement 3 and statement 4 is return to... printFun(2): finding printFun(2) statement 3 at top of stack test3 = 2 test3 = 2 printed by statement 3 and statement 4 is return to... printFun(3): finding printFun(3) statement 3 at top of stack test3 = 3 test3 = 3 printed by statement 3 and statement 4 is return to/from empty stack RunTime = 0.0 Secs

**Now if I try to take the same approach with my Fibonacci code**

with Statement numbers added --with Statement numbers added --

Code: Select all

```
if (lookup[n] == NIL) //statement 0
{
if (n <= 1)
lookup[n] = n; //statement 1
else
lookup[n] = fib(n-1) + fib(n-2); //statement 2
}
return lookup[n]; //statement 3
}
```

**I end up with the following and don't understand how to**

handle the return lookup[n] Statements (#3)

with regard to the Stack --handle the return lookup[n] Statements (#3)

with regard to the Stack --

CALLED ****** fib(5) local n initialized to 5 and statements 3 to 1 pushed on stack fib(4) local n initialized to 4 and statements 3 to 1 pushed on stack fib(3) local n initialized to 3 and statements 3 to 1 pushed on stack fib(2) local n initialized to 2 and statements 3 to 1 pushed on stack fib(1) local n initialized to 1 and lookup[1] = 1 by statement 1*and statement 3 return does what? fib(0) local n initialized to 0 and lookup[0] = 0 by statement 1*and statement 3 return does what? fib(1) fib(2) fib(3)*Probably NOT, Right?

Last edited by kenbrooker on Tue Jan 01, 2019 10:44 pm, edited 25 times in total.

"

*Good Judgment comes from Experience;*

Experience comes from Bad Judgment..."Experience comes from Bad Judgment

### Re: Code optimization techniques

You're welcome

I may make some mistakes/incorrect technical descriptions when using "stack" and "stack frame" However, I think I can roughly explain the issue here. The line (for example)

is not quite correct.fib(5) local n initialized to 5 and statements 3 to 1 pushed on stack

After we see statement 1 does not apply, we move onto statement 2. But it is not treated all in one go. We first see we need "fib(4)", so

*this*creates a new stack frame where we now have local n = 4. (I guess we "freeze" inside this statement in the fib(5) stack frame, and create a new one for fib(4), but I am actually curious how this works in practice with the "overall" stack I'll have to look into it!) We then need fib(3) but this is being called from inside fib(4),

**NOT**as the "second half" of the fib(5) statement 2. Then fib(2) (again, being called from fib(5)->fib(4)->fib(3)->fib(2) so all are on the stack, each with a new frame/local n).

Inside fib(2), we can calculate fib(1) (put it on stack, add fib(1) result to our cache, pop it off in the return) and fib(0) (similarly). Once we have calculated these, we are back in fib(2) and can now add the result of fib(1) + fib(0) to our cache in lookup[2] and return the result of fib(2) - the "return" statement in fib(2) is not considered until after fib(1) and fib(0) have already been added to the stack, populated the lookup, and returned their results to fib(2) stack frame.

Now we're back in fib(3), and we just got fib(2) returned (and put in the cache). Next, we continue with the second half of statement 2 (inside fib(3)), and call fib(1). This is the call where we see lookup[2] (and lookup[1]) are populated, so no further recursion is needed.

We can then return fib(3) to fib(4), and then inside fib(4) we next call fib(2) (already cached), then add fib(4) to the cache and get back to fib(5) (pop our first fib(4) call from the stack). Now we make our second call to fib(3), which is already cached so we're done.

**This is when we have finally finished with the "statement 2" from the fib(5) call.**

In summary, inside fib(5) we FIRST add a new fib(4) to the stack (as

**part**of statement 2), but then we deal with fib(4) completely before popping it off and adding fib(3) to the stack - the first fib(3) call in inside fib(4), not fib(5)). Maybe the "second half" of fib(5) is on the stack (... somewhere), but we do not meet it until we've dealt the everything inside fib(4)'s frame.

So the stack builds up roughly like this:

Code: Select all

```
fib(5) // add fib(5) to stack
fib(5)->fib(4) // add fib(4) to stack
fib(5)->fib(4)->fib(3) // add fib(3) to stack (from inside fib(4) function)
fib(5)->fib(4)->fib(3)->fib(2) // add fib(2) to stack (from inside fib(3) function)
fib(5)->fib(4)->fib(3)->fib(2)->fib(1) // add fib(1) to stack, return it (pop from stack)
fib(5)->fib(4)->fib(3)->fib(2)->fib(0) // add fib(0) to stack, return it (pop from stack)
fib(5)->fib(4)->fib(3)->fib(2) // back to fib(2) , NOW we hit statement 3/ return
fib(5)->fib(4)->fib(3)->fib(1) // add fib(1) to stack (from inside fib(3) function)
fib(5)->fib(4)->fib(3) // return fib(3)
fib(5)->fib(4)->fib(2) // return fib(2)
fib(5)->fib(4) // return fib(4)
fib(5)->fib(3) // add fib(3) to stack (from inside fib(5) function), return it from cache
fib(5)
```

- kenbrooker
**Posts:**129**Joined:**Mon Feb 19, 2018 3:05 am**Location:**Oregon, USA

### Re: Code optimization techniques

*Gee*

Couldn't you be...

Briefer?!

Just kidding!! Look at the two lengthy Posts I inflicted upon you and I am amazed at your

Patience, Speed, "Depth" of Reply, and SUPER Kindness, e.g. "not quite correct"...

Well, my first impression is that I wasn't even close to understanding the Stack...

There's a Hell of a lot more going on than I realized and

I look forward to studying your Reply but,

I just want to Thank You ASAP and

Wish You a Happy New Year!

ps - I don't even know what

a/the "cache" is!

**MHealy**...Couldn't you be...

Briefer?!

Just kidding!! Look at the two lengthy Posts I inflicted upon you and I am amazed at your

Patience, Speed, "Depth" of Reply, and SUPER Kindness, e.g. "not quite correct"...

Well, my first impression is that I wasn't even close to understanding the Stack...

There's a Hell of a lot more going on than I realized and

I look forward to studying your Reply but,

I just want to Thank You ASAP and

Wish You a Happy New Year!

ps - I don't even know what

a/the "cache" is!

"

*Good Judgment comes from Experience;*

Experience comes from Bad Judgment..."Experience comes from Bad Judgment

### Re: Code optimization techniques

Haha, yes I feel like I did repeat myself a little but unfortunately it is quite late (or early ) here so I won't be able to edit it much tonight. The "rambling" nature perhaps tells me I am not familiar enough with the subject to be trying to explain it I am very much open to somebody else coming here with a much more concise/correct explanation.

But when I say cache I just mean your array (lookup) in this case, not anything more technical than that. (As a noun - "the cache" - I am talking about the array; as a verb - "cached" - I am talking about adding something to the array.)

But when I say cache I just mean your array (lookup) in this case, not anything more technical than that. (As a noun - "the cache" - I am talking about the array; as a verb - "cached" - I am talking about adding something to the array.)

- kenbrooker
**Posts:**129**Joined:**Mon Feb 19, 2018 3:05 am**Location:**Oregon, USA

### Re: Code optimization techniques

*Ohhh... Thanks Again!! and I was TOTALLY Kidding about brevity...*

I don't think you rambled at all but then again,

You Level 17s have a High Standard...

I don't think you rambled at all but then again,

You Level 17s have a High Standard...

Last edited by kenbrooker on Sun Dec 30, 2018 11:50 pm, edited 2 times in total.

"

*Good Judgment comes from Experience;*

Experience comes from Bad Judgment..."Experience comes from Bad Judgment

- kenbrooker
**Posts:**129**Joined:**Mon Feb 19, 2018 3:05 am**Location:**Oregon, USA

### Re: Code optimization techniques

Well, I guess I'm feeling stubborn on my 71st Birthday (Geriatric Immunity-eligible?) and not yet ready to abandon my

(Robotic) approach to mapping a recursion, specifically re the Stack...

I think we would both arrive at exactly the same "Stack Map" for my printFun example, several Posts above, and I'd like to look at another much more interesting example, much more like the Fibonacci-by-Memoization causing me trouble, and that is PE Problem 517 aka "A Real Recursion" (where, incidentally, the advantage of Dynamic Programming (DP)

over Recursion is demonstrated to the tune of G(100) being 10 times faster; G(121), 100 times faster; and,

G(144), 1000 times faster(!); and, StackOverflowError for Recursion initiates at about G(8200) )...

As usual, I'll show the PE517 code below, Recursive and DP/Tabulation, and

here is my Stack Map for the recursion --

This is my initial brute-force code for PE517, but serves our purpose, and it includes both the

Recursive and DP versions, with the DP code currently commented out, and

Statements 1 & 3 re printing x1 & x2 are strictly for the purpose of

tracking the mysterious & elusive... "Stack Map" above --

(exactly as all-that-was-executed in printFun...)

Now it's my turn to say I

What are the mystery (Robotic) steps in my Stack Map for Fibonacci by Memoization?!

Specifically, how do I map

(Robotic) approach to mapping a recursion, specifically re the Stack...

I think we would both arrive at exactly the same "Stack Map" for my printFun example, several Posts above, and I'd like to look at another much more interesting example, much more like the Fibonacci-by-Memoization causing me trouble, and that is PE Problem 517 aka "A Real Recursion" (where, incidentally, the advantage of Dynamic Programming (DP)

over Recursion is demonstrated to the tune of G(100) being 10 times faster; G(121), 100 times faster; and,

G(144), 1000 times faster(!); and, StackOverflowError for Recursion initiates at about G(8200) )...

As usual, I'll show the PE517 code below, Recursive and DP/Tabulation, and

here is my Stack Map for the recursion --

A 4 / \ / \ / \ / \ D G 3 2 / \ / \ / \ / \ H K M C 2 1 1 0 / / / \ / \ W R X T 1 0 / \ E S preorder as below 4 3 2 1 0 1 2 1 0 preorder A D H W E S K R G M X T C postorder E S W H R K D X T M C G A inorder E W S H D R K A X M T G C level order A D G H K M C W R X T E S

a = 2.0 x 4 x1 = 4.0 x2 = 4.0 x1 = 3.0 x2 = 3.0 x-1 x-a 3 2 x1 = 2.0 x2 = 2.0 final x1 = 1.0 2 1 1 0 <-- call x1 = 0.0 +one +one +one x1 = 1.0 x1 = 2.0 x2 = 2.0 1 0 "return"s: one +one x1 = 1.0 x1 = 0.0 <-- 9 calls (count x1s only) G(4) = 5.0 via Recursion [1.0, 1.0, 2.0, 3.0, 5.0] via 3 iterations from [1.0, 1.0] via Dynamic Programming/Tabulation *** RunTime = 0.0 Secs

CALLED Printed ********** ******* gaofx(2,4) local x initialized to 4 and statements 4 to 1 pushed on stack and x1 = 4 x1 = 4 printed by statement 1 and statement 2 false and x2 = 4 x2 = 4 printed by statement 3 and gaofx(2,3) called by statement 4 and +gaofx(2,2) pushed on stack gaofx(2,3) local x initialized to 3 and statements 4 to 1 pushed on stack and x1 = 3 x1 = 3 printed by statement 1 and statement 2 false and x2 = 3 x2 = 3 printed by statement 3 and gaofx(2,2) called by statement 4 and +gaofx(2,1) pushed on stack gaofx(2,2) local x initialized to 2 and statements 4 to 1 pushed on stack and x1 = 2 x1 = 2 printed by statement 1 and statement 2 false and x2 = 2 x2 = 2 printed by statement 3 and gaofx(2,1) called by statement 4 and +gaofx(2,0) pushed on stack gaofx(2,1) local x initialized to 1 and statements 4 to 1 pushed on stack and x1 = 1 x1 = 1 printed by statement 1 and statement 2 true so return 1 +gaofx(2,0) on top of stack with local x initialized to 0 and x1 = 0 x1 = 0 printed by statement 1 and statement 2 true so return +1 +gaofx(2,1) on top of stack with local x initialized to 1 and x1 = 1 x1 = 1 printed by statement 1 and statement 2 true so return +1 +gaofx(2,2) on top of stack with local x initialized to 2 and x1 = 2 x1 = 2 printed by statement 1 and statement 2 false and x2 = 2 x2 = 2 printed by statement 3 and gaofx(2,1) called by statement 4 and +gaofx(2,0) pushed on stack gaofx(2,1) with local x initialized to 1 and x1 = 1 x1 = 1 printed by statement 1 and statement 2 true so return 1 (+1 via 2,2?) +gaofx(2,0) on top of stack with local x initialized to 0 and x1 = 0 x1 = 0 printed by statement 1 and statement 2 true so return +1 and Stack Empty!! 9 Calls and Returns 1+1+1+1+1 = 5

This is my initial brute-force code for PE517, but serves our purpose, and it includes both the

Recursive and DP versions, with the DP code currently commented out, and

Statements 1 & 3 re printing x1 & x2 are strictly for the purpose of

tracking the mysterious & elusive... "Stack Map" above --

(exactly as all-that-was-executed in printFun...)

Code: Select all

```
import java.util.Arrays;
class PE517Proc
{
double gaofx(double a, double x)
{
System.out.println(" x1 = " +x); //statement 1
if(x < a) return 1; //statement 2
System.out.println(" x2 = " +x); //statement 3
System.out.println();
return gaofx(a, x-1) + gaofx(a, x-a); //statement 4
}
}
class PE517
{
public static void main(String args [ ])
{
double start = System.currentTimeMillis();
System.out.println();
//------------------------------------------------------------------------------------------------------------------
// CODE FOR RECURSION:
PE517Proc g = new PE517Proc();
double ax = 4.0;
System.out.print("G(" +(int)ax+ ") = ");
System.out.println(g.gaofx(Math.sqrt(ax), ax) );
//------------------------------------------------------------------------------------------------------------------
/*
//------------------------------------------------------------------------------------------------------------------
// CODE FOR DP/TABULATION:
double a = 2.0;
double max = 4.0;
double gaRay[] = new double[(int)(max+1)];
for(int i = 0; i < (int)a; i++)// <--problems if 'a' non-integer sqrt of max
{
gaRay[i] = 1;
}
for(int x = (int)a; x <= max; x++)// <--problems if 'a' non-integer sqrt of max
{
gaRay[x] += gaRay[x-1] + gaRay[(int)(x-a)];// <--problems if 'a' non-integer sqrt of max
} // like Math.sqrt(90)...
System.out.println(Arrays.toString(gaRay));
//------------------------------------------------------------------------------------------------------------------
*/
double finish = System.currentTimeMillis();
System.out.println("RunTime = " + (finish - start)/1000 + " Secs");
}
}
```

*my Stack Maps for printFun and for PE517 are (albeit Robotically) correct and...***"**think**"****"***If somebody else has a better understanding of exactly how this works in terms of "the stack",*

and/or corrections, I'd like to hear themand/or corrections, I'd like to hear them

**"**AND given that no one finds those Maps incorrect:What are the mystery (Robotic) steps in my Stack Map for Fibonacci by Memoization?!

Specifically, how do I map

**"return**(to?/from?)**lookup[n]"**aka a "cache"?*And my apologies,***MHealey**, I'm afraid it's woefully late again in LondonTown...
Last edited by kenbrooker on Tue Jan 01, 2019 10:53 pm, edited 2 times in total.

"

*Good Judgment comes from Experience;*

Experience comes from Bad Judgment..."Experience comes from Bad Judgment

- kenbrooker
**Posts:**129**Joined:**Mon Feb 19, 2018 3:05 am**Location:**Oregon, USA

### Re: Code optimization techniques

MAYBE it starts out like this --PRINTED CALLED lookup[] ****** ******** Fib(5) local n initialized to 5 and Statements 3 to 0 pushed on stack & Statement 0 true and Fib(4) called by Statement 2 and +Fib(3) pushed on stack by Statement 2 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1] Fib(4) local n initialized to 4 and Statements 3 to 0 pushed on stack & Statement 0 true and Fib(3) called by Statement 2 and +Fib(2) pushed on stack by Statement 2 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1] Fib(3) local n initialized to 3 and Statements 3 to 0 pushed on stack & Statement 0 true and Fib(2) called by Statement 2 and +Fib(1) pushed on stack by Statement 2 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1] Fib(2) local n initialized to 2 and Statements 3 to 0 pushed on stack & Statement 0 true and Fib(1) called by Statement 2 and +Fib(0) pushed on stack by Statement 2 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1] Fib(1) local n initialized to 1 and Statements 3 to 0 pushed on stack & Statement 0 true and lookup[1] = 1 by Statement 1 and???[-1, 1, -1, -1, -1, -1, -1, -1, -1, -1] +Fib(0) on top of stack and local n initialized to 0 and Statements 3 to 0 pushed on stack & Statement 0 true and lookup[0] = 0 by Statement 1 and???[0, 1, 1, -1, -1, -1, -1, -1, -1, -1]^^THIS is where lookup[2] has become 1 and I can't (Robotically) figure out... Why?

Statements repeated here for convenience:

Code: Select all

```
if (lookup[n] == NIL) //statement 0
{
if (n <= 1)
lookup[n] = n; //statement 1
else
lookup[n] = fib(n-1) + fib(n-2); //statement 2
}
return lookup[n]; //statement 3
```

Last edited by kenbrooker on Tue Jan 01, 2019 10:37 pm, edited 1 time in total.

"

*Good Judgment comes from Experience;*

Experience comes from Bad Judgment..."Experience comes from Bad Judgment

### Re: Code optimization techniques

I have been doing a bit of reading since I last replied (eg. on Wikipedia), so hopefully I have a better understanding now. I am still open to corrections!

Fundamentally, as far as I understand it,

To go into slightly more detail in this case, let's look at the top of the stack from when fib(2) is first called. We have local variable n set to 2, and we move on to the call into fib(1). We then stop executing anything inside fib(2), add the new fib(1) frame to the stack (with a new local n = 1 and so on), and go through fib(1).

This has no recursive calls, so we quickly get to the "return". We pop fib(1) from the stack, and now go back to fib(2)

We then continue in this function - having both values so we can finish this line: setting lookup[2] = fib(1) + fib(0) = 1 + fib(0) = 1 + 1, then finally returning. If you were to add another "print" statement inside the "fib" call, just before the return, you would see a line from inside fib(2) print at the point where lookup[2] is mysteriously populated.

If we now remember that we called fib(2) inside fib(3), we see we are about to call into fib(1). When we call into fib(1), this is the first time we have called into a function since populating lookup[2]. Nothing has printed since we stated fib(0) (a

Does that help?

Now, how this all happens at a processor/machine code level, I have

Fundamentally, as far as I understand it,

*statements*(i.e. lines of code) are**not**put on the stack in this sense;*subroutines*(i.e. functions) are. A function is not removed from the stack until it "returns", and any inner functions it calls are put on the stack on top of it and dealt with first. The inner function contains information about exactly where it was called from and, when it has returned, it is removed from the stack and the next function down (i.e. the function which called it) continues from where the inner function was called (now knowing the value returned from said function).To go into slightly more detail in this case, let's look at the top of the stack from when fib(2) is first called. We have local variable n set to 2, and we move on to the call into fib(1). We then stop executing anything inside fib(2), add the new fib(1) frame to the stack (with a new local n = 1 and so on), and go through fib(1).

This has no recursive calls, so we quickly get to the "return". We pop fib(1) from the stack, and now go back to fib(2)

*where we left it*, knowing the result of fib(1). We then get to "+ fib(0)", so we do the same with fib(0). Once this completes, we pop it, get back to fib(2), and continue from after the call to fib(0) (with n = 0, and having the results of fib(1) and fib(0) to hand locally [in its own stack frame?]).We then continue in this function - having both values so we can finish this line: setting lookup[2] = fib(1) + fib(0) = 1 + fib(0) = 1 + 1, then finally returning. If you were to add another "print" statement inside the "fib" call, just before the return, you would see a line from inside fib(2) print at the point where lookup[2] is mysteriously populated.

If we now remember that we called fib(2) inside fib(3), we see we are about to call into fib(1). When we call into fib(1), this is the first time we have called into a function since populating lookup[2]. Nothing has printed since we stated fib(0) (a

**long**time ago), but a lot has happened - we went back into fib(2) and populated lookup[2], before returning.Does that help?

Now, how this all happens at a processor/machine code level, I have

**no**idea. And maybe that is what your question is*really*about? How does the computer store which function to go to, where to go to in that function, all the variables it needs and so on? How does it deal with all the statements inside one function, whilst leaving it and working on a completely different function? Hmm... We'll have to ask somebody who programs in assembly... Java is as "low-level" as I go- kenbrooker
**Posts:**129**Joined:**Mon Feb 19, 2018 3:05 am**Location:**Oregon, USA

### Re: Code optimization techniques

Happy New Year and

Muchas Gracias

I was afraid I might have offended you or discouraged you, but you were commendably reading up on what

I must study next re Stacks... Thanks for the Wiki link (at odds, I see already, with Geeks for Geeks)...

And to answer your kind question --

As you have probably noticed I like my pretty Decision Trees and I like tell-tale "print" statements so

not only did I add a "print" just before the "return" but I added "print"s just before Any and

Everything, hopefully nowhere misleadingly, and I want you to see them,

immediately below, ASAP (I haven't "studied" them yet) and

hopefully in corroboration of your esteemed analysis (and

hopefully not boring Everyone Else on

PE.chat to... Death by Details...

IF Any read this far)...

I've even included some

Just in case the above is misleading,

especially re Stack Calls,

here's the short code,

(wherein I do not see

"return lookup[n];"

TWICE!!) --

ps - I think I somehow got an "A" once in Assembly Language and I know a year later

I couldn't even remember the Professor's name, much less the... Language, so

that is most thoughtful and humble of you to imagine

I might be thinking "Deeper" but I will be thrilled

just to ever understand "return lookup[n]" and,

I am delighted you are a Java Brother...

even at about 1.0 am on Big Ben...

Muchas Gracias

**MHealy**...I was afraid I might have offended you or discouraged you, but you were commendably reading up on what

I must study next re Stacks... Thanks for the Wiki link (at odds, I see already, with Geeks for Geeks)...

And to answer your kind question --

*Yes, your Super Reply HELPS*would be an understatement, especially --*"If you were to add another "print" statement inside the "fib" call, just before the return"*...As you have probably noticed I like my pretty Decision Trees and I like tell-tale "print" statements so

not only did I add a "print" just before the "return" but I added "print"s just before Any and

Everything, hopefully nowhere misleadingly, and I want you to see them,

immediately below, ASAP (I haven't "studied" them yet) and

hopefully in corroboration of your esteemed analysis (and

hopefully not boring Everyone Else on

PE.chat to... Death by Details...

IF Any read this far)...

I've even included some

**MHealy**"Depth"!lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1] fib(5) called: if(lookup[n] == NIL) true if(n <= 1) false so lookup[n] gets/calls fib(n-1) + fib(n-2) lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1] fib(4) called: if(lookup[n] == NIL) true if(n <= 1) false so lookup[n] gets/calls fib(n-1) + fib(n-2) lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1] fib(3) called: if(lookup[n] == NIL) true if(n <= 1) false so lookup[n] gets/calls fib(n-1) + fib(n-2) lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1] fib(2) called: if(lookup[n] == NIL) true if(n <= 1) false so lookup[n] gets/calls fib(n-1) + fib(n-2) lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1] fib(1) called: if(lookup[n] == NIL) true if(n <= 1) true so lookup[n] gets n lookup[] = [-1, 1, -1, -1, -1, -1, -1, -1, -1, -1] return lookup[n] called lookup[] = [-1, 1, -1, -1, -1, -1, -1, -1, -1, -1] <-- Note: No change in lookup[] from fib(0) called: before return lookup[n] called... if(lookup[n] == NIL) true (which does make sense via if(n <= 1) true so lookup[n] gets n fib(n) = fib(n-1) + fib(n-2), lookup[] = [0, 1, -1, -1, -1, -1, -1, -1, -1, -1] the latter NIL...) return lookup[n] called lookup[] = [0, 1, 1, -1, -1, -1, -1, -1, -1, -1] <-- the... sticky point for me and return lookup[n] called What's with these DOUBLE return lookup[n]s?! How does the code even get to those two "println"s again lookup[] = [0, 1, 1, -1, -1, -1, -1, -1, -1, -1] without first having to print lookup[] and fib(1) called: "fib(n) called:"?! lookup[] = [0, 1, 1, -1, -1, -1, -1, -1, -1, -1] return lookup[n] called lookup[] = [0, 1, 1, 2, -1, -1, -1, -1, -1, -1] return lookup[n] called lookup[] = [0, 1, 1, 2, -1, -1, -1, -1, -1, -1] fib(2) called: lookup[] = [0, 1, 1, 2, -1, -1, -1, -1, -1, -1] return lookup[n] called lookup[] = [0, 1, 1, 2, 3, -1, -1, -1, -1, -1] return lookup[n] called lookup[] = [0, 1, 1, 2, 3, -1, -1, -1, -1, -1] fib(3) called: lookup[] = [0, 1, 1, 2, 3, -1, -1, -1, -1, -1] return lookup[n] called lookup[] = [0, 1, 1, 2, 3, 5, -1, -1, -1, -1] return lookup[n] called^^^Fibonacci(5) = 5

Just in case the above is misleading,

especially re Stack Calls,

here's the short code,

(wherein I do not see

"return lookup[n];"

TWICE!!) --

Code: Select all

```
class GeekFibonacciMemoization //w/o public... and apparently unnecessary
{
int MAX = 10; //w/o final... and apparently unnecessary
int NIL = -1; //w/o final... and apparently unnecessary
int lookup[] = new int[MAX];
// Function to initialize NIL values in lookup table
void _initialize()
{
for (int i = 0; i < MAX; i++)
lookup[i] = NIL;
}
// Function for nth Fibonacci number
int fib(int n)
{
System.out.println();
System.out.println();
System.out.println("lookup[] = " +Arrays.toString(lookup));
System.out.println("fib(" +n+ ") called:");
if (lookup[n] == NIL) //statement 0
{
System.out.println(" if(lookup[n] == NIL) true");
if (n <= 1)
{
System.out.println(" if(n <= 1) true so lookup[n] gets n");
lookup[n] = n; //statement 1
}
else
{
System.out.println(" if(n <= 1) false so lookup[n] gets/calls fib(n-1) + fib(n-2)");
lookup[n] = fib(n-1) + fib(n-2); //statement 2
}
}
System.out.println(" lookup[] = " +Arrays.toString(lookup));
System.out.println(" return lookup[n] called");
return lookup[n]; //statement 3
}
public static void main(String[] args)
{
GeekFibonacciMemoization f = new GeekFibonacciMemoization();
System.out.println();
int n = 5;
f._initialize();
System.out.println(" Fibonacci(" +n+ ") = " + f.fib(n));
}
}
```

I couldn't even remember the Professor's name, much less the... Language, so

that is most thoughtful and humble of you to imagine

I might be thinking "Deeper" but I will be thrilled

just to ever understand "return lookup[n]" and,

I am delighted you are a Java Brother...

even at about 1.0 am on Big Ben...

"

*Good Judgment comes from Experience;*

Experience comes from Bad Judgment..."Experience comes from Bad Judgment

### Re: Code optimization techniques

It's only the return section of the previously called functions:

The first calls of fib(5), fib(4), fib(3) and fib(2) did not immediately return - they need to call fib(n-1) and fib(n-2) first.

So read it as follows:

Stack: fib(5)

(A.1) Call fib(5) -> nothing known; call fib(4) and fib(3)

Stack: A

To call: A(fib(4), fib(3))

(B.1) Call fib(4) -> nothing known; call fib(3) and fib(2)

Stack: A, B

To call: B(fib(3), fib(2)), A(fib(3))

(C.1) Call fib(3) -> nothing known; call fib(2) and fib(1)

Stack: A, B, C

To call: C(fib(2), fib(1)), B(fib(2)), A(fib(3))

(D.1) Call fib(2) -> nothing known; call fib(1) and fib(0)

Stack: A, B, C, D

To call: D(fib(1), fib(0)), C(fib(1)), B(fib(2)), A(fib(3))

(E.1) Call fib(1) -> Is clear; add to known values and return 1

Stack: A, B, C, D, E

To call: D(fib(0)), C(fib(1)), B(fib(2)), A(fib(3))

(E.2) Return of E

Stack: A, B, C, D

To call: fib(0), fib(1), fib(2), fib(3)

(F.1) Call fib(0) -> Is clear; add to known values and return 0

Stack: A, B, C, D, F

To call: C(fib(1)), B(fib(2)), A(fib(3))

(F.2) Return of F

Stack: A, B, C, D

To call: C(fib(1)), B(fib(2)), A(fib(3))

(D.2) Now fib(2) is clear, as fib(2) = fib(1) + fib(0) = 1 + 0 = 1; store fib(2)=1 and return 1

Stack: A, B, C

To call: C(fib(1)), B(fib(2)), A(fib(3))

(G.1) Call fib(1) a second time but now the value is known; just return the value 1

Stack: A, B, C, G

To call: B(fib(2)), A(fib(3))

(G.2) return fib(2) = 1

Stack: A, B, C

To call: B(fib(2)), A(fib(3))

(C.2) fib(3) is now clear -> so add the value fib(3) = 2 to the table and then return

Stack: A, B

To call: B(fib(2)), A(fib(3))

(H.1) Call fib(2) again; now the value is known -> so look at the table and return

Stack: A, B, H

To call: A(fib(3))

(H.2) Return the value of fib(2)

Stack: A, B

To call: A(fib(3))

(B.2) Now we can calculate fib(4) = fib(3) + fib(2) = 3, store this value and return

Stack: A

To call: A(fib(3))

(I.1) Call fib(3) again; now the value is known -> look at the table and return

Stack: A, I

To call: (nothing more!)

(I.2) Return the value of fib(3)

Stack: A

To call: (nothing)

(A.2) Now fib(5) knows the values of fib(4) and fib(3) (B and I) and it stores and returns the value 5

Stack: (nothing -> only main)

To call: (nothing)

--> Finished

The first calls of fib(5), fib(4), fib(3) and fib(2) did not immediately return - they need to call fib(n-1) and fib(n-2) first.

So read it as follows:

Stack: fib(5)

(A.1) Call fib(5) -> nothing known; call fib(4) and fib(3)

Stack: A

To call: A(fib(4), fib(3))

(B.1) Call fib(4) -> nothing known; call fib(3) and fib(2)

Stack: A, B

To call: B(fib(3), fib(2)), A(fib(3))

(C.1) Call fib(3) -> nothing known; call fib(2) and fib(1)

Stack: A, B, C

To call: C(fib(2), fib(1)), B(fib(2)), A(fib(3))

(D.1) Call fib(2) -> nothing known; call fib(1) and fib(0)

Stack: A, B, C, D

To call: D(fib(1), fib(0)), C(fib(1)), B(fib(2)), A(fib(3))

(E.1) Call fib(1) -> Is clear; add to known values and return 1

Stack: A, B, C, D, E

To call: D(fib(0)), C(fib(1)), B(fib(2)), A(fib(3))

(E.2) Return of E

Stack: A, B, C, D

To call: fib(0), fib(1), fib(2), fib(3)

(F.1) Call fib(0) -> Is clear; add to known values and return 0

Stack: A, B, C, D, F

To call: C(fib(1)), B(fib(2)), A(fib(3))

(F.2) Return of F

Stack: A, B, C, D

To call: C(fib(1)), B(fib(2)), A(fib(3))

(D.2) Now fib(2) is clear, as fib(2) = fib(1) + fib(0) = 1 + 0 = 1; store fib(2)=1 and return 1

Stack: A, B, C

To call: C(fib(1)), B(fib(2)), A(fib(3))

(G.1) Call fib(1) a second time but now the value is known; just return the value 1

Stack: A, B, C, G

To call: B(fib(2)), A(fib(3))

(G.2) return fib(2) = 1

Stack: A, B, C

To call: B(fib(2)), A(fib(3))

(C.2) fib(3) is now clear -> so add the value fib(3) = 2 to the table and then return

Stack: A, B

To call: B(fib(2)), A(fib(3))

(H.1) Call fib(2) again; now the value is known -> so look at the table and return

Stack: A, B, H

To call: A(fib(3))

(H.2) Return the value of fib(2)

Stack: A, B

To call: A(fib(3))

(B.2) Now we can calculate fib(4) = fib(3) + fib(2) = 3, store this value and return

Stack: A

To call: A(fib(3))

(I.1) Call fib(3) again; now the value is known -> look at the table and return

Stack: A, I

To call: (nothing more!)

(I.2) Return the value of fib(3)

Stack: A

To call: (nothing)

(A.2) Now fib(5) knows the values of fib(4) and fib(3) (B and I) and it stores and returns the value 5

Stack: (nothing -> only main)

To call: (nothing)

--> Finished

- kenbrooker
**Posts:**129**Joined:**Mon Feb 19, 2018 3:05 am**Location:**Oregon, USA

### Re: Code optimization techniques

*Dear*

Sincerest thanks for your conspicuous patience in replying with such clarity, via precision, in

such a necessarily long reply and, no doubt, with 100% accuracy...

I guess I was fooled by my "printFun" and PE517 examples into thinking that,

with sufficient print statements, I could track the Stack (from which

print statements apparently/obviously are not executed); however,

with the complication(?) of a "return lookup[n]" table,

I can see by your multitudinous reply that

I can not even get close...

If you could possibly explain how "return lookup[n];" is not only called but

diagnostically printed out

I would be forever indebted but,

I don't mean to bore you...

(Maybe you are saying that "return lookup[n]" serves the same purpose as

the simpler "return" statement(s) so common in most other

recursive functions?)

The Bottom Line is

Thanks Again!!

Ken

**v6ph1**...Sincerest thanks for your conspicuous patience in replying with such clarity, via precision, in

such a necessarily long reply and, no doubt, with 100% accuracy...

I guess I was fooled by my "printFun" and PE517 examples into thinking that,

with sufficient print statements, I could track the Stack (from which

print statements apparently/obviously are not executed); however,

with the complication(?) of a "return lookup[n]" table,

I can see by your multitudinous reply that

I can not even get close...

If you could possibly explain how "return lookup[n];" is not only called but

diagnostically printed out

**twice**, in my (simplistic) output,I would be forever indebted but,

I don't mean to bore you...

(Maybe you are saying that "return lookup[n]" serves the same purpose as

the simpler "return" statement(s) so common in most other

recursive functions?)

The Bottom Line is

Thanks Again!!

Ken

"

*Good Judgment comes from Experience;*

Experience comes from Bad Judgment..."Experience comes from Bad Judgment

### Re: Code optimization techniques

I just changed your output so for each return, the current n is reported:

-> the return is called twice as it's called by different function calls.

For example fib(2) (the 4th call of fib) is startet, but it is still in progress until the result of fib(0) is returned.

-> the return is called twice as it's called by different function calls.

For example fib(2) (the 4th call of fib) is startet, but it is still in progress until the result of fib(0) is returned.

Expand

- kenbrooker
**Posts:**129**Joined:**Mon Feb 19, 2018 3:05 am**Location:**Oregon, USA

### Re: Code optimization techniques

*Excellent Idea!!*

The evidence was there all along and I changed my code accordingly and

your annotations in red are most clear and helpful...

I'm hoping it's still possible to write code to generate

the exact same lengthy Stack History that

you kindly provided...

So far I'm fairly successful with the following

simple recursive code...

**v6ph1**...The evidence was there all along and I changed my code accordingly and

your annotations in red are most clear and helpful...

I'm hoping it's still possible to write code to generate

the exact same lengthy Stack History that

you kindly provided...

So far I'm fairly successful with the following

simple recursive code...

Code: Select all

```
int mystery(int value)
{
if(value <= 10) return value * 3;
else return value + mystery(mystery(value / 5));
}
```

*I'm pretty confident the Stack History*

looks like this --

looks like this --

STACK: (Top to the Right)

*******

m(45)

m(45)1, m(9) returns 27

m(45)1

m(45)2, m(27)

m(45)2, m(27)1, m(5) returns 15

m(45)2, m(27)1,

m(45)2, m(27)2, m(15)

m(45)2, m(27)2, m(15)1, m(3) returns 9

m(45)2, m(27)2, m(15)1

m(45)2, m(27)2, m(15)1, m(9) returns 27

m(45)2, m(27)2, m(15)1

m(45)2, m(27)2, m(15)12 returns 15 + 27 = 42

m(45)2, m(27)12 returns 27 + 42 = 69

m(45)12 returns 45 + 69 = 114

m(value)1 refers to the inner mystery() call;

m(value)2, to the outer call...

*and so far my code*

generates --

generates --

[STACK] (Top to the Right) ************************** mystery(45) called and 45 > 10 calls mystery(mystery(9)) so Push mystery(-45) on Stack [-45, 0, 0, 0, 0, 0, 0, 0, 0, 0] mystery(9) called and 9 <= 10 so Push mystery(9) on Stack [-45, 9, 0, 0, 0, 0, 0, 0, 0, 0] and mystery(9) returns 27 so <-- Pop mystery(9) off Stack [-45, 0, 0, 0, 0, 0, 0, 0, 0, 0] mystery(27) called and 27 > 10 calls mystery(mystery(5)) so Push mystery(-27) on Stack [-45, -27, 0, 0, 0, 0, 0, 0, 0, 0] mystery(5) called and 5 <= 10 so Push mystery(5) on Stack [-45, -27, 5, 0, 0, 0, 0, 0, 0, 0] and mystery(5) returns 15 so <-- Pop mystery(5) off Stack [-45, -27, 0, 0, 0, 0, 0, 0, 0, 0] mystery(15) called and 15 > 10 calls mystery(mystery(3)) so Push mystery(-15) on Stack [-45, -27, -15, 0, 0, 0, 0, 0, 0, 0] mystery(3) called and 3 <= 10 so Push mystery(3) on Stack [-45, -27, -15, 3, 0, 0, 0, 0, 0, 0] and mystery(3) returns 9 so <-- Pop mystery(3) off Stack [-45, -27, -15, 0, 0, 0, 0, 0, 0, 0] mystery(9) called and 9 <= 10 so Push mystery(9) on Stack [-45, -27, -15, 9, 0, 0, 0, 0, 0, 0] and mystery(9) returns 27 so <-- Pop mystery(9) off Stack [-45, -27, -15, 0, 0, 0, 0, 0, 0, 0] . . . mystery(45) = 114

*I haven't yet figured out how to "unwind" the mystery(mystery()) calls to*

mystery(15), mystery(27) and mystery(45), as indicated by the

negative numbers (and, by the way,

the code does not include

memoization)...

If by any chance I can duplicate that

METICULOUS Stack History that

you provided, I will

let you know...

Thanks Again!!

Ken

mystery(15), mystery(27) and mystery(45), as indicated by the

negative numbers (and, by the way,

the code does not include

memoization)...

If by any chance I can duplicate that

METICULOUS Stack History that

you provided, I will

let you know...

Thanks Again!!

Ken

Last edited by kenbrooker on Sun Jan 06, 2019 6:16 am, edited 3 times in total.

"

*Good Judgment comes from Experience;*

Experience comes from Bad Judgment..."Experience comes from Bad Judgment

- kenbrooker
**Posts:**129**Joined:**Mon Feb 19, 2018 3:05 am**Location:**Oregon, USA

### Re: Code optimization techniques

*Finally, a BRIEF Post to confirm my progress toward*

an automated Stack History --

I'm confident that the

correct Stack History

looks like this --

an automated Stack History --

I'm confident that the

correct Stack History

looks like this --

STACK: (Top to the Right)

*******

m(45)

m(45)1, m(9) returns 27

m(45)1

m(45)2, m(27)

m(45)2, m(27)1, m(5) returns 15

m(45)2, m(27)1,

m(45)2, m(27)2, m(15)

m(45)2, m(27)2, m(15)1, m(3) returns 9

m(45)2, m(27)2, m(15)1

m(45)2, m(27)2, m(15)1, m(9) returns 27

m(45)2, m(27)2, m(15)12 returns 15 + 27 = 42

m(45)2, m(27)12 returns 27 + 42 = 69

m(45)12 returns 45 + 69 = 114

m(value)1 refers to the mystery() call;

m(value)2, to the mystery(mystery()) call...

And my automated output is --[STACK] (Top to the Right) ******* m[45, 0, 0, 0] m[45, 9, 0, 0] returns 27 m[45, 0, 0, 0] m[45, 27, 0, 0] m[45, 27, 5, 0] returns 15 m[45, 27, 0, 0] m[45, 27, 15, 0] m[45, 27, 15, 3] returns 9 m[45, 27, 15, 0] m[45, 27, 15, 9] returns 27 m[45, 27, 15, 0] returns 15 + 27 = 42 m[45, 27, 0, 0] returns 27 + 42 = 69 m[45, 0, 0, 0] returns 45 + 69 = 114 mystery(45) = 114 RunTime = 0.0 Secs

"

*Good Judgment comes from Experience;*

Experience comes from Bad Judgment..."Experience comes from Bad Judgment

- kenbrooker
**Posts:**129**Joined:**Mon Feb 19, 2018 3:05 am**Location:**Oregon, USA

### Re: Code optimization techniques

*PROGRESS REPORT: Reminder -- My final goal is an automated*

Stack History for Fibonacci by Memoization but...

For the simplest Fibonacci by Recursion --

Stack History for Fibonacci by Memoization but...

For the simplest Fibonacci by Recursion --

Code: Select all

```
int fib(int n)
{
if (n <= 1) return n;
else return fib(n-1) + fib(n-2);
}
```

*As a first step toward a Stack History, simply inserting*

System.out.println(" fib(" +n+ ") Called");

*at the*

top of function fib gives --

top of function fib gives --

fib(5) Called fib(4) Called fib(3) Called fib(2) Called fib(1) Called fib(0) Called fib(1) Called fib(2) Called fib(1) Called fib(0) Called fib(3) Called fib(2) Called fib(1) Called fib(0) Called fib(1) Called

*Yielding this Preorder Recursion Tree for fib(5) (and*

illustrating all the repeated computations,

e.g. the entire fib(3) sub-tree twice) --

illustrating all the repeated computations,

e.g. the entire fib(3) sub-tree twice) --

fib(5) / \ / \ / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) / \ / \ / \ fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) / \ fib(1) fib(0)

*From which one can ascertain the following*

Stack History (with patience?) --

Stack History (with patience?) --

Top of Stack to the Right: 5cld 5 4cld 5 4 3cld 5 4 3 2cld 5 4 3 2 1cld returns fib(1) = 1 5 4 3 2top 5 4 3 2 0cld returns fib(0) = 0 5 4 3 2top returns fib(2) = fib(1)+fib(0) = 1 5 4 3top 5 4 3 1cld returns fib(1) = 1 5 4 3top returns fib(3) = fib(2)+fib(1) = 2 5 4top 5 4 2cld 5 4 2 1cld returns fib(1) = 1 5 4 2top 5 4 2 0cld returns fib(0) = 0 5 4 2top returns fib(2) = fib(1)+fib(0) = 1 5 4top returns fib(4) = fib(3)+fib(2) = 3 5top 5 3cld 5 3 2cld 5 3 2 1cld returns fib(1) = 1 5 3 2top 5 3 2 0cld returns fib(0) = 0 5 3 2top returns fib(2) = fib(1)+fib(0) = 1 5 3 1cld returns fib(1) = 1 5 3top returns fib(3) = fib(2)+fib(1) = 2 5top returns fib(5) = fib(4)+fib(3) = 5 cld = Called top = Top of Stack; Possibly Called...

*And my best code to date replicates the above although*

I am still pessimistic about replicating Fibonacci by

Memoization, i.e. including a "lookup" table,

though it should take fewer steps!

I am still pessimistic about replicating Fibonacci by

Memoization, i.e. including a "lookup" table,

though it should take fewer steps!

Top of Stack to the Right: fib[5, 0, 0, 0, 0, 0] 5cld fib[5, 4, 0, 0, 0, 0] 4cld fib[5, 4, 3, 0, 0, 0] 3cld fib[5, 4, 3, 2, 0, 0] 2cld fib[5, 4, 3, 2, 1, 0] 1cld returns 1 fib[5, 4, 3, 2, 0, 0] 2top fib[5, 4, 3, 2, 0, 0] 0cld returns 0 fib[5, 4, 3, 2, 0, 0] 2top returns 1 fib[5, 4, 3, 0, 0, 0] 3top fib[5, 4, 3, 0, 1, 0] 1cld returns 1 fib[5, 4, 3, 0, 0, 0] 3top returns 2 fib[5, 4, 0, 0, 0, 0] 4top fib[5, 4, 0, 2, 0, 0] 2cld fib[5, 4, 0, 2, 1, 0] 1cld returns 1 fib[5, 4, 0, 2, 0, 0] 2top fib[5, 4, 0, 2, 0, 0] 0cld returns 0 fib[5, 4, 0, 2, 0, 0] 2top returns 1 fib[5, 4, 0, 0, 0, 0] 4top returns 3 fib[5, 0, 0, 0, 0, 0] 5top fib[5, 0, 3, 0, 0, 0] 3cld fib[5, 0, 3, 2, 0, 0] 2cld fib[5, 0, 3, 2, 1, 0] 1cld returns 1 fib[5, 0, 3, 2, 0, 0] 2top fib[5, 0, 3, 2, 0, 0] 0cld returns 0 fib[5, 0, 3, 2, 0, 0] 2top returns 1 fib[5, 0, 3, 0, 1, 0] 1cld returns 1 fib[5, 0, 3, 0, 0, 0] 3top returns 2 fib[5, 0, 0, 0, 0, 0] 5top returns 5 fib[0, 0, 0, 0, 0, 0] 0top cld = Called top = Top of Stack; Possibly Called... Fibonacci(5) = 5 RunTime = 0.0 Secs

Last edited by kenbrooker on Fri Jan 11, 2019 4:58 am, edited 1 time in total.

"

*Good Judgment comes from Experience;*

Experience comes from Bad Judgment..."Experience comes from Bad Judgment