CODEWITHSUNDEEP
javascriptstringfunctionrecursion
user1822124
user1822124

Reputation: 21

Converting a loop into a recursive function

I wrote a function yesterday to count the number of "a" characters in a string. My teacher told me to refactor the code into a recursive function and I don't really know how to do so.

I would like some feedback on the subject, and by the way I'm an absolute beginner in JavaScript. 

function numberOfA(n){
var numberA =0;

for (i=0; i<=n.length; i++){

    if(n.charAt(i)== "a"  ){
        numberA++;}
    }
return numberA;

}

to call the function following piece of code : 

var n = prompt("type a word");
var output = numberOfA(n);

alert (output);

Thanks in advance !

Upvotes: 2

Views: 3404

Answers (5)

chip
chip

Reputation: 3279

<!DOCTYPE html><html lang="en"><body><script>
var foo = function foo() {
console.log(arguments.callee); // logs foo()
// callee could be used to invoke recursively the foo function (e.g. arguments.callee())
}();
</script></body></html>

arguments.callee function will call the currently being executed method.

Upvotes: -1

&#211;scar L&#243;pez
&#211;scar L&#243;pez

Reputation: 236004

Try this:

function numberOfA(n) {
    return n == "" ? 0 : (n.charAt(0) == "a" ? 1 : 0) + numberOfA(n.substring(1))
}

Here's how it works:

  • If n is the empty string, return 0 and finish the recursion. This is the base case of the recursion.
  • Else if the character at the first position in the string is an "a" add one, if not add zero and either way advance the recursion by removing the first character from the string. This is the recursive step of the recursion.

As you can see, every recursive solution must have at least a base case and a recursive step.

Upvotes: 0

LetterEh
LetterEh

Reputation: 26696

The goal of recursion is to make a function which calls itself.
You might have mutual-recursion -- function A calls function B, calls function A... but that's certainly not needed here, and is better suited for when you know that you need to do two distinct things (one per function) and know that you need to do them in a leapfrog pattern.

Where recursion comes into play is when you're thinking about loops.
Normally, when you're doing things with loops, you might end up having two or three loops inside of one another.
Instead of worrying about managing loops, recursion is a way of thinking about what happens in a single-iteration of a loop, and writing ONLY the code needed to do that.

A really simple example of singular recursion might be to log all elements of an array to the console.
This is not a practical example -- it's a trivial example which has most of the pieces you need to make practical examples.

var array = [ "one", "two", "three", "four" ];

function listNextItem (array, index) {
    var item = array[index];
    if (!item) { return; }

    console.log(item);
    listNextItem(array, index + 1);
}

listNextItem(array, 0);

I've created a very simple function which looks like the inside of your innermost loop.
It sets an item variable, based on array[index].
If it doesn't exist, we're done, and we can return out of the function, so we don't try to go on forever (this is very important in recursion).

If it does exist, we log the item's value. Then we call the exact same function, and pass it the exact-same array, but we pass it the value of index + 1.

Did this change anybody's life, or make loops obsolete?
Not really.

But it's the first step to getting recursion.

The next step is getting a return from recursion.

function recursiveAddOne (current, max) {
    if (current === max) { return current; }
    return 1 + recursiveAddOne(current + 1, max);
}

var total = recursiveAddOne(0, 3); // === 3 + 1 + 1 + 1
total; // 6

Normally in my return statement, I'd be sending the answer back to the variable in the outside world.
I'm still doing that, but here I'm adding a call to the same function, as part of my return.

What does that do?
Well, the outside function can't return a value until the inside function returns.
The inside function can't return a value until ITS inside function returns...

...and it goes all the way down until my termination-condition is met. That condition returns a value to its outer function. That outer function returns that added value to ITS outer function... ...all the way up to where the outermost function gets handed the value of all of the other functions put together, and then returns THAT to the outside world.

It's like giving each Russian Matryoshka ("babushka") doll a piece of work.
You start with the biggest one, and go all the way inside to the tiniest one.
The tiniest one does its work first, and hands it back to the next one, which does its work and hands that back... ...all the way back until you're outside again.

Upvotes: 7

Vyacheslav Voronchuk
Vyacheslav Voronchuk

Reputation: 2463

function numberOfA(n, count){
    if(!n.length) {  
        return count;
    }

    if(n.charAt(i)== "a") {
        ++count;
    }

    return numberOfA(n.substr(1), count);
}
var numberA = numberOfA('asdfafeaa', 0);

Upvotes: 0

Sam I am says Reinstate Monica
Sam I am says Reinstate Monica

Reputation: 31184

Well, the basic concept of recursion is solving a problem with a smaller version of itself.

You have a function, numberOfA which gives you the length of a string(or maybe substring).

So let's say you have the string "javascript' the first string is at index 2.

It's logical to say that the number of as in your string is equal to 1 plus the number of as in the entire substring after the first a.

So what you do, is you add 1 to the number of as in the substring vascript


So here's some psudocode

function numA(str)
{
    var substring = substr(index_of_first_a, str.length - index_of_first_a
    return 1 + numA(substring);
}

Upvotes: 1

Related Questions