Apparently recursion takes up more memory space than nested for loops (I'm talking about 4-5 for loops) and I lose grades for the same.
Erlang, Elixir, Haskell, APL, Prolog, etc.
I'm tempted to say you have the question backwards: loops are somewhat arbitrary; why do imperative languages need loops? Imperative/OO languages need loops because they have no other way to write iterative code. Functional languages do: recursion. Recursion is not a "feature" of functional languages, it's a natural consequence of their design. On the other hand, early imperative languages didn't support recursion at all and even modern ones support it poorly, forcing them to use something else to iterate—loops.
Recursion, by itself, does a poor job of reflecting intent. if we have a for-loop, we know that we're taking n steps or iterating over every element of a list; if we have a while loop, we know we're going until we hit some condition. Not much, but recursion doesn't even give us that.
This is where higher-order functions come in. Map, filter, fold and friends package up common recursive patterns into library functions that are easier to use than direct recursion and signal intent. When you see a map, you know that it will apply a function to every element in a list and nothing more. Moreover, when you use map, you know the iteration is going to be correct—you can't make off-by-one errors or skip elements in the list. The same idea holds for all the other higher-order functions available in functional languages' libraries, and there are a lot.
TLDR: It's worth knowing, but don't piss off your professor because you will need to pass their class.
It is a useful tool. Knowing how to do recursion is better than not knowing.
> My CS teacher told me to avoid recursion when possible.
Bad CS teacher. There are some algorithms that are much more elegant and easier to build in a recursive manner (i.e., walking a tree being one).
> Apparently recursion takes up more memory space than nested for loops (I'm talking about 4-5 for loops) and I lose grades for the same.
That really depends upon what local variables the recursive routine allocates. But, unless you are studying for building embedded systems with seriously constrained memory space, the difference in memory is negligible in today's typical systems with gigabytes available. And an easier to understand algorithm in recursive form would outweigh a difference in memory usage anyway.
> I lose grades for the same.
Again, bad CS teacher. Unless the problem statement explicitly indicated to not use a recursive routine, a recursive solution should be graded on whether it fulfills the rest of the problem statement requirements, not on the mere fact that it is recursive.
It’s a handy concept and tool but not practical/relevant for a lot of real world/day to day stuff.
And of course there’s the obligatory joke:
What’s the B in Benoit B Mandelbrot stand for?
Benoit B Mandelbrot ;)
Most definitely. OP should get into a different class or university. I'd be concerned about the program generally if someone is teaching these ideas
You don't know. Maybe she wants them to recognize and use folds whenever possible, rather than using low level recursion all the time. You know what they say: "Someone has to write recursive functions, but it does not have to be you!"
The dogmatic systems department wishes to replace recursion with something more concrete; the dogmatic theory department with something more abstract.
Much easier!
Most commonly used programming languages will be slower to recurse than to loop using "for" or "while". Not all languages have tail call optimization and it can be difficult to reason about when tail call optimization is applicable.
That said, there are programming languages where recursion is literally how you loop, so it's not that it's bad so much as that these languages are in the minority.
The classic, literally "textbook", example is solving the Fibonacci sequence
Where F(N) = F(N-1) + F(N-2)
AND F(0) = 1
AND F(1) = 1
You have a pair of base cases / definitions
But then the rest of the solution is trivial to implement (even most-obviously, to some people) implemented in its recursive form :)
It's not that far from a function like the Collatz sequence, which will may just earn you a Fields medal if you're able to say for certain what it will return for all given inputs.
Recursion uses space on the call stack. The concern is not so much that you'll be using more memory, it's that the call stack has a fixed size and you might blow past that size, which will cause your program to terminate.
The comparison between recursion and "nested for loops" seems a bit off - generally it's recursion vs a single loop.
Whether it's best to avoid recursion depends on many factors. In any case, even when I do want to use iteration, it's often easiest to first formulate the algorithm as a recursive one, and then change it to use iteration.
More generally, you might look into the benefits of tail call optimization, especially in Scheme.
Recursion is something you don't use so often, but it's a useful pattern for traversing trees. It has its uses, but it can make the code a bit harder to understand.
Recursion is the perfect solution to a handful of problems (eg tree traversal)
...so long as you have the memory to do it!
Back in highschool, I wrote a linear (ie iterative) octree traverser in C++
It was about 250 lines (not counting comments and whitespace ... printed it was about 10 pages (50 lines to the page on that old printer!)
And it worked! But I did it that way because I hadn't seen recursion except as an example of solving the Fibonacci sequence (for which it is distinctly ill-prepared!)
When I learned about recursion properly a few years later, I rewrote that ~250 line function down to under one page printed (with ample whitespace and comments)...it was maybe 30 lines long in its recursive form
That all said ... solving for recurrence relations is 100% "worth it" IF (and only if) the recursive runtime and/or memory usage is "too much". How "much" is "too much"? That's going to depend on the problem at hand.
Linear/iterative solutions are [almost] always faster than their recursive cousins ... but they're often not nearly as intuitive
------------
[0] https://hvcc.edu
It's true that it's rarely used in production quality code, but nonetheless it's sometimes useful and you should have a good command of writing recursive code.
Recursion-the-concept is sometimes the only way to solve a problem. If you want to calculate the total number of leaves in a tree structure, the algorithm is clear: recursively sum the number of leaves in each branch. Recursion is just a way of saying "for this loop, we will need to maintain some kind of stack to track our location".
Conveniently, most languages have a stack built-in in the form of a function call graph. This allows us to elegantly and concisely express recursive algorithms by simply writing functions that call themselves, exactly like the formal definition of recursion. You don't have to do it that way - you can create your own stack data structure and manually manage it, and it'll still be a recursive algorithm. But that's probably a bad idea unless you have good reason to believe that working with your language's built-in stack has limitations that are important for your use case - limited size or poor performance, perhaps.
In fact, a few days ago I implemented a flood fill algorithm for a drawing app I am developing. I later converted it to an iterative solution. Here’s a comparison between the two solutions
For most languages I use I try to avoid it though most of the time. You can get bugs because the stack gets to deep.
The main issue with recursion is not even speed, it's the fact the stack is not too large. As far as I remember, by default 2MB on Windows. You can easily keep 2GB of data in std::vector or an equivalent. And if by mistake you try to put 20TB there, most languages have decent ways to handle out of memory errors.
Still, there're rare cases when recursion is good. These are the cases when performance doesn't matter, you know for sure the depth will never exceed ~200k, but recursion helps a lot with code size and readability.
For a data processing command line type lightwight dev prof services type position
Lame
I didn't get it but pretended to keep a good attitude thru the ordeal
I have needed it tho for a side project -- walking a bookmark tree in Javascript
This video seems reasonable and agrees with prof
I do remember old xml parsers blowing up in all sorts of ways due to bugs and or malformed xml -- usually recursion-related
Sure it works on most, but usually it is for prototyping the algo. It is really bad pratcice not separating the space of the programflow (stack) and algo's flow (heap). You will realize it when you get stackoverflow - actually this is the main reason to the forum's name.
Under support I mean "it works well", and not "try it, if you are lucky, it may work".
If you are not using a school example like print the first 10 fibonacci with recursion, you will get a stackoverflow error. By support now I mean, the language not only allows, but encourages the readable, original form of an algorithm.
Some things are easier with recursion, like traversing a tree. But outside of those I'd avoid using recursion. In other words, only use recursion if you have a good reason.
Your typical code base will use very little recursion, if any.
It is generally less readable, and relatively easy to blow up your stack.
If your prof is trying to teach you software engineering, he or she is right to ask you to choose the simplest way to express something. If your prof was teaching you about a recursive data structure, you would be considering the tradeoffs of a recursive implementation versus another one.
Some languages/environments have tail call optimization. Some do not.