javascript - Converting a loop into a recursive function - Stack Overflow

admin管理员组

文章数量:1401401

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 !

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 !

• javascript
• string
• function
• recursion

Share Improve this question Follow edited Nov 13, 2012 at 22:29 Chad 19.6k44 gold badges5353 silver badges7575 bronze badges asked Nov 13, 2012 at 21:52 user1822124user1822124 2111 silver badge22 bronze badges 7

• 1 Just FWIW: There's exactly zero reason to use a recursive algorithm to count how often a specific character occurs in a string. The assignment is quite silly. Not your problem, but in case you were wondering "why" the answer is "for no good reason." – T.J. Crowder Commented Nov 13, 2012 at 21:56
• its a silly requirement as a linearsearch is much better for this functionality, but I would probably replace the for statement with a recursive call for the next char as Sam I am suggested. – Frank Thomas Commented Nov 13, 2012 at 21:57
• @T.J.Crowder I'm not going to argue that it's a trivial purpose, which really has no practical benefit in terms of output. But I will say that it's a pretty safe way to dip a person's toes into the concept of recursion, rather than through binary-tree navigation, or parsing large structures of densely-nested objects/arrays in JS. – LetterEh Commented Nov 13, 2012 at 22:00
• @T.J.Crowder do you teach your introductory programming classes by giving your students problems from production? – Sam I am says Reinstate Monica Commented Nov 13, 2012 at 22:02
• @Norguard: Yeah. I'd sure like to e up with a better problem, but it's late here and time for me to retire. As you say, you wouldn't want to have to throw too much at people all at once. – T.J. Crowder Commented Nov 13, 2012 at 22:02

 |  Show 2 more ments

5 Answers 5

Sorted by: Reset to default 7

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 es 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.

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);
}

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);

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.

<!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.

本文标签： javascriptConverting a loop into a recursive functionStack Overflow