recursion - writing a recursive method into a non recursive (java) -

recursion - writing a recursive method into a non recursive (java) -

i'm little bit confused understanding how recursion works.

basically have replace recursive methods non recursive methods.

for example, recursive method:

public key min() { if (isempty()) { homecoming null; } homecoming min(root).key; } private node min(node x) { if (x.left == null) { homecoming x; } else { homecoming min(x.left); } } public key max() { if (isempty()) { homecoming null; } homecoming max(root).key; } private node max(node x) { if (x.right == null) { homecoming x; } else { homecoming max(x.right); } } public key floor(key key) { node x = floor(root, key); if (x == null) { homecoming null; } else { homecoming x.key; } } private node floor(node x, key key) { if (x == null) { homecoming null; } int cmp = key.compareto(x.key); if (cmp == 0) { homecoming x; } if (cmp < 0) { homecoming floor(x.left, key); } node t = floor(x.right, key); if (t != null) { homecoming t; } else { homecoming x; } } public key ceiling(key key) { node x = ceiling(root, key); if (x == null) { homecoming null; } else { homecoming x.key; } } private node ceiling(node x, key key) { if (x == null) { homecoming null; } int cmp = key.compareto(x.key); if (cmp == 0) { homecoming x; } if (cmp < 0) { node t = ceiling(x.left, key); if (t != null) { homecoming t; } else { homecoming x; } } homecoming ceiling(x.right, key); }

and effort of doing non-recursively:

public key min() { if (isempty()) { homecoming null; } homecoming min(root).key; } private node min(node x) { while (x.left !=null){ x = x.left; } homecoming x; } public key max() { if (isempty()) { homecoming null; } homecoming max(root).key; } private node max(node x) { while (x.right!=null){ x = x.right; } homecoming x; } public key floor(key key) { node x = floor(root, key); if (x == null) { homecoming null; } else { homecoming x.key; } } private node floor(node x, key key) { if (x == null) { homecoming null; } int cmp = key.compareto(x.key); if (cmp == 0) { homecoming x; } if (cmp < 0) { while (x.left != null){ x = x.left; if (x ==null){ homecoming null; } } } node t = x.right; while (x.right != null){ x = x.right; if (x == null){ homecoming null; } } if (t != null){ homecoming t; } else{ homecoming x; } }

i'm asking if have right idea.

yes, have right idea.

private node min(node x) { if (x.left == null) { homecoming x; } else { homecoming min(x.left); } }

this non-recursive solution of function above.

private node min(node x) { while (x.left !=null){ x = x.left; } homecoming x; }

you should take @ http://en.wikipedia.org/wiki/dynamic_programming, particularly memoization.

edit: take @ similar thread: way go recursion iteration

java recursion