Any tips for turning iterative into recursive?

JavaScript
1

let me know if the question is too vague, but i was trying to turn iterative into recursive function (sorting algo) and i keep getting confused with declaring variables that i then used for iteration, and now want to use for a return/termination condition within the same func. i suppose i could embed a second function in the function but thought i’m probably missing a trick here

function selectionSort(array) {
  let arrSlice = array
  let i=
  //for(let i=0;i<array.length-1;i++){
    arrSlice = array.slice(i)
    const min = Math.min(...arrSlice);
    const index = arrSlice.indexOf(min, 0);
    [array[i],array[index+i]] = [array[index+i],array[i]];
  //selectionSort(?)
    i++;
  //}
  return array;
}
console.log(  selectionSort([4,3,2,8,345,123,43,32,5643,63,123,43,55,1,234,92])  )
2

You know that i needs to start at 0. Think of a way to define an extra function parameter where i would default to 0 if no value was specified. Then, all you need to do after the i++; line is return the array when you know that each value of i has been used or return a recursive call to the function again specifying the applicable value of i as an argument.

3

you mean like this:

function selectionSort(array, eye) {
  if(!eye){i=0}
  if(eye>=array.length-1){return array}
  let arrSlice = array
  //let i=
  //for(let i=0;i<array.length-1;i++){
    arrSlice = array.slice(i)
    const min = Math.min(...arrSlice);
    const index = arrSlice.indexOf(min, 0);
    [array[i],array[index+i]] = [array[index+i],array[i]];
  
    i++;
    selectionSort(array, i)
  //}
  return array;
}
console.log(  selectionSort([4,3,2,8,345,123,43,32,5643,63,123,43,55,1,234,92])  )

regardless, it is working perfectly. thank you.
i am a little bemused that i don’t seem to be declaring i in this code tho, but i’m getting no complaints in vsCode/chrome.

4

You are implicitly declaring i, making it a global variable. Given how common i is as a variable name, you probably don’t want to do that.

1 Like
5

I was thinking more along the lines of creating a second parameter i that has a default value of 0.

EDIT: The following two lines really should be one line.

  let arrSlice = array
  arrSlice = array.slice(i)
6

do you mean more like this, which works fine (the other one failed in FCC editor):

function selectionSort(array, eye) {
 // if(!eye){let i=0}else{let i=eye}
 let i = eye || 0;

[edit noted, thanks]

which i could then do like this???:

function selectionSort(array, i) {
 // if(!eye){let i=0}else{let i=eye}
 i = i || 0;
  if(i>=array.length-1){return array}

(bit worried if i’ve done another implicit, global declaration)

7

I would research default values for function parameters. You are still not taking advantage of them here.

8 
function selectionSort(array, i=0) {
 //i = i || 0;
  if(i >= array.length-1){return array}
  //let i=

???

1 Like
9

and because it’s a function parameter (with default value) i don’t worry about declaring a variable in the recursive function? i suppose that is a common trick?

10

Default parameter values are a pretty common trick, yeah. You’ll see it for recursion sometimes.

It’s good to practice, but this is a somewhat awkward problem for recursion in my opinion. Recursion is a nice fit when you have to repeat a task an unknown number of times, but you have a fixed length arry here, so recursion doesn’t buy you anything. It just makes the logic a bit harder to read at a glance.

It is a useful learning tool for exploring function calls, scope, and return values, but it’s a pretty rare case when you need recursion in the wild. Some sort of tree traversal is the usual best use case for recursion.

1 Like
11

so, i found one example where we don’t know how many iterations there will be and i eventually realised i don’t need default values for parameters and i still can ‘declare’ them this way avoiding a recursive assignment.
(e.g. i had originally written the below code with this function declaration:
function binarySearch(searchList, value, mid=-1, midIndex=-1, arrayPath=[], list=searchList) {
when i don’t need the -1 at all.)

but my question is, would this be considered a reasonable implementation in the wild? many parameters, and one given a default assignment to another parameter, seems somewhat convoluted.

function binarySearch(searchList, value, mid, midIndex, arrayPath=[], list=searchList) {
  if(list.length <= 0){return 'Value Not Found'}
  else if(mid == value){return arrayPath}

  if(value > mid){ list = list.slice(midIndex+1)
  }else if(value < mid){ list = list.slice(0, midIndex) }

  midIndex = Math.floor((list.length-1)/2)
  mid = list[midIndex]
  arrayPath.push(mid)
  return binarySearch(list, value, mid, midIndex, arrayPath)
}

const testArray = [
  0, 1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
  23, 49, 70
]; 
console.log('result:',  binarySearch(testArray, 5)  )

EDIT: I just realised i don’t need the list=searchList at all and can just change to:
function binarySearch(list, value, mid, midIndex, arrayPath=[]) {
Oh well, i will leave my post as is for what it’s worth. And i still don’t think i get anything out of recursion here, as a do-while loop seems just fine.

12

With the call binarySearch(testArray, 5) , what exactly is supposed to be returned? Your function returns [13, 5]. Shouldn’t it return the index of where the 5 is located?

13

no, i belive its supposed to return the values (13,5)

14

What does 13 represent and what does 5 represent in the returned array?

15

they are the center values of the array as given on previous step
ie 13 is the middle value on original array, then 5 in next step

16

Then that is not really a binary search. Binary search is typically used to find the index of a value in a sorted array and return “not found” if not present.

17

i didn’t name it as such, but you might want to tell FCC

18

sorry, maybe i should have linked that originally

19

although the indices are in the code. look like it’s just matter of the ouput

20

Yes, having the instructions of the problem is always best.

For this challenge, we want you to show your work - how you got to the target value… the path you took!

Showing the path is not typically the point of a binary search which is why I questioned the approach.

1 Like