This forum is now read-only. Please use our new forums! Go to forums

0 points
Submitted by Craig
almost 12 years

Seriously, will I ever need recursion?

Even with the new lesson and its patient teachings, I’m still totally bamboozled by recursion. I can sort of see what the code is attempting to do, but if you asked me to work out a problem from scratch with a blank page, I wouldn’t know where to start.

Is recursion really something I need to know? Should I keep banging my head against walls of examples until I get it, or is it so rarely used in the real world that I can forget about it? It sounds like for just about everything I’d ever need, I could just use a ‘while’ loop, which I find infinitely easier to understand.

I ultimately want to program simple games. Is recursion used for such things? Like, ever?

If you’re a programmer and use recursion a lot, I’d love to know how and why!

Thanks!

Answer 4fd765800ef82b00030244ea

8 votes

Permalink

Recursive thinking is really important in programming. It helps you break down bit problems into smaller ones. Often, the recursive solution can be simpler to read than the iterative one. Recursion is used all the time, in nearly field, in nearly every language. :)

It is hard, and you won’t get it right away, but it’s good to know something about. If you collaborate, the other programmers will probably use it at some point and you’ll to be able to read their code (if nothing else).

But if you have a taste, you can probably move on and review this stuff when you see it again. Computer science students usually take a term worth of classes to really nail it.

points
Submitted by steph-vd
almost 12 years

1 comments

Michele Moneywell over 11 years

Settling on a recursive solution means limited thinking. This is because the problem can be solved by iteration. Iteration can do everything recursion can do (plus much more) without the problems of recursive programming.

Answer 500f1dc3fc36510002025fa9

3 votes

Permalink

One common example of useful recursion (meaning, not fibonacci or factorial) is depth-first traversal of trees.

For example

// this function returns the first leaf of a binary tree,
// found by depth-first traversal

function traverseTree(tree){
   // if this node of the tree is a leaf, return it
   if(tree.isLeaf){    
        return tree.leaf;
    }
    // otherwise search the left and right branches of the tree
    else{
        return (traverseTree(tree.leftBranch) || traverseTree(tree.rightBranch));
    }
}

Of course, this function is ‘tree recursive’ which means that given a big enough tree, the function call stack will overflow quickly.

points
Submitted by ehaliewicz
over 11 years

1 comments

Michele Moneywell over 11 years

Exactly why recursion should NOT be used. A simple while loop should be used instead.

Answer 501bc87b129c500002027e8b

2 votes

Permalink

The recursion also allows you to apply an Inductive Solution, since both are practically the same: a base case and the inductive hypothesis.

Induction is studied strongly in computer science to solve many problems, like the tree one quoted above by ehaliewicz, the sorting problem, graphs and many other problems in algorithms.

Induction = Recursion.
It allows you to reach an elegant and simple solution that many times can’t be “translated” to iterative ways (I can’t code any iterative method for the Quick Sort algorithm).

I know it could be confusing at the beginning, but trust me, soon you’ll see it naturally.

PS: sorry bad English

points
over 11 years

1 comments

Michele Moneywell over 11 years

Wrong. Any recursive problem can be solved by iteration (looping). Also, recursion is slower because there are more systems resources and overhead involved.

Answer 50319104fa8f1000020040d7

1 vote

Permalink

You absolutely should not use recursive programming, so it is okay if you do not understand it.

First of all, any problem that can be solved recursively can also be solved by iteration (which means using a loop, such as for, while, or do…while).

Second of all, each time the function calls itself, it creates substantial overhead. Space must be allocated and a copy of the variables and parms must be made. This also takes extra processing time. It can result in running out of memory and stack overflow problems. In the Fibonacci problem, you are even severely warned to limit the number of years to 40 or less because otherwise your browser would be likely to freeze and crash! None of these worries exist with using iteration, and it is no problem to handle a “number of years” argument greater than 40.

Third, recursive code is difficult to understand and update. It takes “head scratching” until one “gets it.” On the other hand, ood code, such as by using a loop, is straight forward and easy to update.

Fourth, recursive programming is error-prone. There are always warning about it.

Fifth, due to the substantial overhead that recursive programming incurs, you are limited in what you can do. A recursive process calling itself more than 40 times becomes problematic.

So, since recursive programming has so much against it, why use it? Answer–you should not use it! Instead, you should rethink the problem and figure out how to solve it with a loop.

Here is the Fibonacci problem done with iteration: function mygrowBeanstalk(years) { var height=0, yearAgo=1, twoYearsAgo=1, i=2; //i var is optional if (years > 0 && years <= 2) height=1; while (years>2){ height = yearAgo + twoYearsAgo; years = years - 1; twoYearsAgo = yearAgo; yearAgo = height; i++; //optional, shows year–the fib sequence number console.log(i, height); //optional, shows growth each year } return height; } console.log(“height is “ + mygrowBeanstalk(50));

points
Submitted by Michele Moneywell
over 11 years

Answer 503684bc833790000204c8b5

0 votes

Permalink

Iterations only do work DOWN the stack.
Recursive functions can do work UP AND DOWN the stack

Very simple examples:

For() {
//work down stack }

function() {
//work down stack function() //work back up stack }

points
Submitted by Connel Hooley
over 11 years