JS: Recursion

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
azule
Saved
Posts: 2132
Joined: Mon Jul 26, 2010 9:45 pm UTC
Location: The land of the Golden Puppies and Rainbows

JS: Recursion

Postby azule » Sun Jul 20, 2014 8:57 am UTC

I've tried to do some recursive functions recently in mostly modern browsers (Firefox and Chrome) and have found that the functions aren't returning the string but instead "undefined". I'll start with an example:

Code: Select all

var recursion = function(exit) {
   if (exit) {
      return "string";
   } else {
      recursion(true);
   }
}
recursion();

This returns undefined. If set as recursion(true) from the start, it returns "string" as intended.

Anyone have a clue why this does not work?

I'm sure I used recursion in the past, but not sure if I ever returned a value or just executed another function. Maybe this never worked...

Related question: is there ever good case for recursion over simple loops?
Image

If you read this sig, post about one arbitrary thing you did today.

I celebrate up to six arbitrary things before breakfast.
Time does drag on and on and contain spoilers. Be aware of memes.

User avatar
Xenomortis
Not actually a special flower.
Posts: 1421
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: JS: Recursion

Postby Xenomortis » Sun Jul 20, 2014 9:18 am UTC

When you call recursion, you're not returning it's result.
That's why your function ultimately returns "undefined" - it's not actually returned anything

Code: Select all

...
} else {
    return recursion(true)
}
...


azule wrote:Related question: is there ever good case for recursion over simple loops?

Some problems are more naturally expressed/solved in a recursive manner.
Image

User avatar
azule
Saved
Posts: 2132
Joined: Mon Jul 26, 2010 9:45 pm UTC
Location: The land of the Golden Puppies and Rainbows

Re: JS: Recursion

Postby azule » Wed Jul 23, 2014 2:34 am UTC

Maybe a link would be helpful. I'm trying to understand why this doesn't work. Your answer has code that is different than what I wrote.

I know that recursion is required in other languages, such as XSLT, but what do you mean by natural?

Edit: Oh, I see now. You fixed the code. I thought you meant "you" in the general sense, meaning that recursion doesn't do that. I see now that you fix it by making sure it returns something on that first call (and that every call returns a value down the chain). *pops self on the head*

Thanks a million!
Image

If you read this sig, post about one arbitrary thing you did today.

I celebrate up to six arbitrary things before breakfast.
Time does drag on and on and contain spoilers. Be aware of memes.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: JS: Recursion

Postby EvanED » Wed Jul 23, 2014 4:47 am UTC

Xenomortis wrote:
azule wrote:Related question: is there ever good case for recursion over simple loops?

Some problems are more naturally expressed/solved in a recursive manner.
As a more concrete answer, pretty much the prototypical example of something that is much more naturally written recursively even in a very-imperative language like C are tree operations where you have to descend, do something, come back up, and do something else, as in any traversal. (I'm not sure what your background is, so don't know how much this makes sense. If you know what linked lists are but not trees, a tree is like a linked list but where instead of each node having a single successor, it can have multiple.)

Without recursion, you essentially have to maintain a stack yourself. Here's an example tree traversal:

Code: Select all

def recursive_traverse(node):
    print "("
    if node.left:
        recursive_traverse(node.left)
    print node.value
    if node.right:
        recursive_traverse(node.right)
    print ")"

class Node:
    def __init__(self, v, l = None, r = None):
        self.value = v
        self.left = l
        self.right = r

two = Node(2)
three = Node(3)
four = Node(4)
two_plus_four = Node(" + ", two, four)
six_times_three = Node(" * ", two_plus_four, three)
recursive_traverse(six_times_three)  # should print "(((2) + (4)) * (3))"
I actually tried writing an iterative version... but I don't trust myself to do something correct without thinking about it more than I feel like right now. (It's getting late.)

Another example of a class of problems that are neatly solved with recursion are backtracking algorithms. A canonical example of a backtracking algorithm would be a maze-solving algorithm. If it comes to an intersection, it picks a direction and tries to go that way, in a recursive call. When it runs out of ways to go, it returns up the call chain and tries the next path.

Code: Select all

# Consider 'position' to be a tuple (row,col)

def north(position):
    return (position.row - 1, position.col)

def east(position):
    return (position.row, positon.col + 1)

# similar for south & west

class Maze:
    def can_go_north_from(self, position):
        .... # check the actual maze walls
    ... # other directions

def _maze_solve_helper(maze, position, visited):
    if position in visited:
        return None
    visited.add(position)
    if maze.at_finish(position):
        return []
    if maze.can_go_north_from(position):
        solution_maybe = maze_solve(maze, north(position))
        if solution_maybe:
            return ["north"] + solution_maybe
    if maze.can_go_east_from(position):
        solution_maybe = maze_solve(maze, east(position))
        if solution_maybe:
            return ["east"] + solution_maybe
    if maze.can_go_south_from(position):
        solution_maybe = maze_solve(maze, south(position))
        if solution_maybe:
            return ["south"] + solution_maybe
    if maze.can_go_west_from(position):
        solution_maybe = maze_solve(maze, west(position))
        if solution_maybe:
            return ["west"] + solution_maybe
    return None

def maze_solve(maze):
    return _maze_solve_helper(maze, maze.starting_position(), set())
or something like that.

[Incidentally, these two problems are not actually all that far apart.]

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: JS: Recursion

Postby korona » Wed Jul 23, 2014 6:17 am UTC

Yeah, depth first search is really ugly to code iteratively. While the usual DFS can relatively easily be done by using an explicit stack it gets really ugly (and inefficient!) if you need something like the pre- and post-order traversals of the graph.

But in general iterative versions will almost always be faster, especially when tail-call optimizations cannot be performed.

User avatar
azule
Saved
Posts: 2132
Joined: Mon Jul 26, 2010 9:45 pm UTC
Location: The land of the Golden Puppies and Rainbows

Re: JS: Recursion

Postby azule » Sat Jul 26, 2014 4:05 am UTC

EvanED wrote:If you know what linked lists are but not trees
The opposite, actually. Javascript and HTML, of course, per my example. That does make sense. Then it can "dive" an arbitrary level deep.

While I don't totally get your examples (can't read C as well as JS), I get the gist. I was previously working on a very complicated code, using recursion, where it would follow a path and return to find another path at the same starting point and eventually move on from that starting point. I tried an iteration instead but it wasn't making sense. Hopefully, since I know how to solve my issue, recursion will again be my answer.

"tail-call optimizations", korona? I assume that this does not apply to Javascript...

Wow, looking at some recursion examples online, I see this:
Developer Drive wrote:

Code: Select all

function recursMe(param) {
     if (param < 0) {     //base case
         return -1;
      }
     else {

          //some code here
          recursMe(param);
      }
}
According to the solution up-thread, this code will not do as intended.
Image

If you read this sig, post about one arbitrary thing you did today.

I celebrate up to six arbitrary things before breakfast.
Time does drag on and on and contain spoilers. Be aware of memes.

User avatar
jaap
Posts: 2084
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: JS: Recursion

Postby jaap » Sat Jul 26, 2014 7:53 am UTC

azule wrote:Wow, looking at some recursion examples online, I see this:
Developer Drive wrote:

Code: Select all

function recursMe(param) {
     if (param < 0) {     //base case
         return -1;
      }
     else {

          //some code here
          recursMe(param);
      }
}
According to the solution up-thread, this code will not do as intended.

The second code path indeed doesn't return a value, so it would not work if there was intended to be a return value.
What is worse here is that it is an infinite recursion for any param>=0. I would have expected it to say something like recursMe(param-1); there. Maybe the 'some code here' could decrease param but it is pretty bad to leave that out in code intended to be an example.

User avatar
chridd
Has a vermicelli title
Posts: 824
Joined: Tue Aug 19, 2008 10:07 am UTC
Location: ...Earth, I guess?
Contact:

Re: JS: Recursion

Postby chridd » Tue Jul 29, 2014 10:32 am UTC

azule wrote:"tail-call optimizations", korona? I assume that this does not apply to Javascript...
I don't know if any (widely-used) browsers use tail-call optimization. The idea behind tail-call optimization is that, if calling another function (especially a recursive call) is the last thing a function does, then the computer doesn't actually need to return back to the original function or remember anything about the original call. So if you have something like:

Code: Select all

function factorial(n, accum) {
   if(n <= 1) return accum;
   return factorial(n-1, accum*n);
}

factorial(3, 1);
factorial(3,1) calls factorial(2,3) which calls factorial(1,6), which then returns 6. Without tail-call optimization, factorial(1,6) has to return back to factorial(2,3) which returns to factorial(3,1) which returns to the main program, and it has to keep information about the local variables for each of those calls; with tail-call optimization, factorial(1,6) can return directly to the main program, and it doesn't have to store the local variables for each call once the recursive call is made.
Another way to look at it is that with tail-call optimization, the compiler turns the recursive call to factorial into a loop.
~ chri d. d. /tʃɹɪ.di.di/ (Phonotactics, schmphonotactics) · she(?)(?(?)(?))(?(?(?))(?))(?) · Forum game scores
mittfh wrote:I wish this post was very quotable...
flicky1991 wrote:In both cases the quote is "I'm being quoted too much!"
chridd (on Discord) wrote:
Dummy wrote:Sorry You're Gay Dads
SYG'D


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 10 guests