java - Can't change variable while doing recursion -
public static void main(string[] args) { int[] = { 1, 2, 3, 4, 5 }; int[] b = new int[5]; rekursiq(a, b, 0, 0, 1); } static void rekursiq(int[] a, int[] b, int index, int start, int check) { if (index == b.length){ system.out.println(java.util.arrays.tostring(b)); } else { (int = start; < a.length; i++) { b[index] = a[i]; rekursiq(a, b, index + 1, + 1, check + 1); } } }
now question is: instead of b.length
in recursion bottom want place int check
, , make check
go +1
on every going there, , something. while (check < b.length)
go if statement, else return; can't seem 1) increase value , 2) make while correctly. don't know why.
i think best try was
static void rekursiq(int[] a, int[] b, int index, int start, int check) { if (check > b.length) { return; } else { if (index == check) { system.out.println(java.util.arrays.tostring(b)); } else { (int = start; < a.length; i++) { b[index] = a[i]; rekursiq(a, b, index + 1, + 1, check + 1); } } } }
but did not work, , hope 1 of can tell me why , how fix it.
the value of check
increase when method called recursively. however, problem have independent of check
.
the problem
let me start repeating abhishrp briefly mentioned: in particular case, want either use loop iterate on elements in array, or recursion, not use loop inside of recursive method. reason following: @ each step in recursion, look @ 1 element: element @ position index
.
the solution
so, how recursively copy array? let assume have source array (in code a
) , empty destination array (in code b
). now, we know how copy single element of array, namely destination[index] = source[index]
, , can imagine copying array copying first element, , copying subarray starting @ second element. note knowing how copy single element in array implies knowing how copy array containing 1 element.
this leads following recursion, turn code shortly after:
- if given index dereferences last element in array, copy last element.
- otherwise, copy element @ current index, , copy subarray starting @ next index.
or expressed in java:
static void copyvaluesfromsourcetodestinationstartingatindex(int[] source, int[] destination, int index) { if (isindexoflastelementinarray(index, destination)) { destination[index] = source[index]; } else { destination[index] = source[index]; copyvaluesfromsourcetodestinationstartingatindex(source, destination, index + 1); } } static boolean isindexoflastelementinarray(int index, int[] array){ return index == array.length - 1; }
note have many parameters in code: parameter check
index
, want check whether index still inside bounds of array. don't know intended variable start
though - seems somehow got confused there because of loop.
sidenote
also, small justification on why true
-branch of if
-statement in above code copy last element instead of returning nothing if index out of bounds in code. it's reasonable did. argument "we trivially know how copy empty array" didn't seem natural "knowing how copy single element implies knowing how copy array consisting of single element". encourage adjust code "copy empty array" base-case, because removes duplication, , more importantly, allows copy empty arrays (for above implementation fail horribly).
code
i tried give comparison between iterative , recursive approach:
public static void main(string[] args) { int[] = {1, 2, 3, 4, 5}; int[] copyofausingiteration = copyarrayusingiteration(a); int[] copyofausingrecursion = copyarrayusingrecursion(a); assert(arrays.equals(copyofausingiteration, copyofausingrecursion)); assert(copyofausingiteration != a); assert(copyofausingrecursion != a); system.out.println(java.util.arrays.tostring(copyofausingiteration)); system.out.println(java.util.arrays.tostring(copyofausingrecursion)); } static int[] copyarrayusingiteration(int[] arraytocopy) { int[] result = new int[arraytocopy.length]; for(int index = 0; index < result.length; index++){ result[index] = arraytocopy[index]; } return result; } static int[] copyarrayusingrecursion(int[] arraytocopy){ if (arraytocopy.length == 0){ return new int[0]; } else { int[] result = new int[arraytocopy.length]; copyvaluesfromsourcetodestinationstartingatindex(arraytocopy, result, 0); return result; } } static void copyvaluesfromsourcetodestinationstartingatindex(int[] source, int[] destination, int index) { if (isindexoflastelementinarray(index, destination)) { destination[index] = source[index]; } else { destination[index] = source[index]; copyvaluesfromsourcetodestinationstartingatindex(source, destination, index + 1); } } static boolean isindexoflastelementinarray(int index, int[] array){ return index == array.length - 1; }
Comments
Post a Comment