Hello and welcome to our community! Is this your first visit?
Enjoy an ad free experience by logging in. Not a member yet? Register.

# Thread: How to go through a table using recursivity?

1. ## How to go through a table using recursivity?

Hi guys, I need to convert a table of strings numbers (like 10x4+5x2+...) into one integer using recursivity.
I need to change that kind of code:

Code:
```for(var i=0; i<myArray.length; i++) {
myArray[i] = parseInt(myArray[i], 10);
}```
for something using recursivity (no loops) to go through every entries of my table. Can you help me?

(The code isn't complete, I know I have to use if charAt(i) == "x" or if charAt(i) == "+")

Thanks!

• So you will have to write a mathematical parser essentially? Should it be able to cope with operator priority? This would really be a big deal ...

Or maybe I didn't understand your requirement? Do you really have lots of table cells with mathematical expressions that you need to parse/evaluate into a single integer result per cell?

• That is definitely a task better handled by two nested loops - one for the table rows and one inside it for the cells in the row.

There is no recursive solution that would map in any meaningful way to the structure of the data so while it would be possible to write a less efficient recursive version of the code it would not only use a lot more memory and run slower - it would also be much harder to maintain.

You should only use recursion where it maps to the task in a meaningful way.

• Code:
```for(var i=0; i<myArray.length; i++) {
myArray[i] = parseInt(myArray[i], 10);
}```
can be written without a loop as:

Code:
`myArray=myArray.map(Math.floor);`
if your table is shaped like a ladder, it can't be recursively iterated.
recursion is for deeply nested objects, like a folder structure.

• Maybe I wasn't clear enough... I learned how to go through my table by using recursivity so I wanted to apply the same method for a string, but I'm still stuck.

s is the string (for example "14x10+2x1"). The function str is then supposed to return 142.

Code:
```var str = function(s){

var i = 0;

var helper = function(s) {

if(i < s.length) {

var t = s.substring(i, s.length)
var stringNum = parseInt(t, 10);
if( t.charAt(i) == "x" ) stringNum *= t.charAt(i+1);
if( t.charAt(i) == "+" ) stringNum += t.charAt(i+1);

i++;
}
return stringNum;
}
return helper(s);
};```
I don't know where I made a mistake... it only returns 14. How can I do to make the function read "x" and "10" and the rest of the string ? Thanks

• A good way to debug those kinds of calculations is to write down the values of variables for each step:

Example: s="14x10+2x1"

1 - i = 0
2 - call helper()
3 - i < s.length, so t = "14x10+2x1"
4 - stringNum = 14
5 - t[0] is not "x" and not "+"
6 - i = 1
7 - stringNum = 14 will be returned to the function str
8 - helper(s) = 14 will be returned from str

So there is no calculation because there is parsing beyond the first numerical value ... an no recursion

• Will it fix the problem if I change the parsing for
Code:
`var stringNum += parseInt(t, 10);`

• if you wanted to avoid the much-despised eval...

Code:
```var str=function(s){
return eval(s.replace(/x/gi,"*"))
}

you could make a dynamic script...

Code:
```var str = function (s){
var scr = document.createElement("script");
scr.type = "text/javascript";
scr.text = "ans = " + s.replace(/x/gi,"*") + ";";
document.body.appendChild(scr);
document.body.removeChild(scr);
return ans;
}

although I suspect they amount to much the same thing...

• I can't use neither eval or dynamic programming... The key of this exercise is to use recursion.

• As this is supposed to be your exercise, I can only give you more hints

1 - Let's hope that you don't have to take care of operator priority (so you can just go right to left)
2 - call your function with the current string
3 - Start from the right of the current string, extract the number and the operator and use it for the expression like "number operator yourfunction(restofstring)". If there is no operator you end the recursion and return the number

Example: 14x10+2x1
step 3: inside of yourfunction: extract 1 and x, return 1*yourfunction("14x10+2")
step 3: inside of yourfunction: extract 2 and +, return 2+yourfunction("14x10")
step 3: inside of yourfunction: extract 10 and x, return 10*yourfunction("14")
step 3: inside of yourfunction: just return 14 => end of recursion
one level up: return 10*14 = 140 => end of recursion
one level up: return 2+140 = 142 => end of recursion
one level up: return 1*142 = 142 => end of recursion
one level up: alert(142) => result

• ## Users who have thanked devnull69 for this post:

123jo (12-13-2012)

• Thanks Devnull69, I almost got it! I have a tiny problem left, how can I extract the 1? When I try with parseInt(s) it automatically takes 14...
I tried to extract it with s[i] where i = s.length-1 but it won't work if the number has more than 1 number (like 10)...and I don't even know if it's supposed to work with a string... Thanks for your help again!

Code:
```var str = function(s){

var i = s.length-1;

var helper = function(s) {

if(i >= 0) {

var t = parseInt(s, 10);
var stringNum = "";

i--;

if( s.charAt(i) == "x" ) stringNum += t*str(s.substring(0,i));
if( s.charAt(i) == "+" ) stringNum += t+str(s.substring(0,i));

}
return stringNum;
}
return helper(s);
};```

• You should specify the number base you are working with as the second parameter to parseint

If you don't then it will interpret 0x17 as the number 23 instead of as 0 times 17.

• Anyone has an idea of how I can get the last integer of a string? Parsing doesn't seem to work...

• Originally Posted by 123jo
Anyone has an idea of how I can get the last integer of a string? Parsing doesn't seem to work...

<script type = "text/javascript">

Code:
```var str = "1234a56d";
str = str.replace(/[^\d]/gi,"");
var len = str.length;
var x = str.charAt(len-1);

var str = "14x10+2x1123";
var x = str.match(/\d+\D*/gi);
var len = x.length;
var y = Number(x[len-1].replace(/[^\d]/g,""));

</script>```

• More like this
Code:
```function getLastInteger(current) {
var i = current.length-1;
while(!isNaN(parseInt(current.substring(i), 10))) i--;
return parseInt(current.substring(i+1), 10);
}