The tag has no usage guidance.

learn more… | top users | synonyms

111
votes
11answers
12k views

Is there anything that can be done with recursion that can't be done with loops?

There are times where using recursion is better than using a loop, and times where using a loop is better than using recursion. Choosing the "right" one can save resources and/or result in fewer lines ...
96
votes
8answers
32k views

Recursion or while loops

I was reading about some development interview practices, specifically about the technical questions and tests asked at interviews and I've stumbled quite a few times over sayings of the genre "Ok you ...
57
votes
18answers
52k views

In plain English, what is recursion?

The idea of recursion is not very common in real world. So, it seems a bit confusing to the novice programmers. Though, I guess, they become used to the concept gradually. So, what can be a nice ...
46
votes
17answers
5k views

Recursion without factorial, Fibonacci numbers etc

Almost every article I can find about recursion includes the examples of factorial or Fibonacci Numbers, which are: Math Useless in real life Are there some interesting non-math code examples to ...
41
votes
4answers
12k views

Why doesn't Java have optimization for tail-recursion at all?

From what I have read: The reason is because it is not easy to determine which method will actually be called as we have inheritance. However, why doesn't Java at least have tail-recursion ...
39
votes
4answers
4k views

What's the difference between recursion and corecursion?

What's the difference between these? Recursion Corecursion On Wikipedia, there is little information and no clear code explaining these terms. What are some very simple examples explaining these ...
30
votes
8answers
24k views

What methods are there to avoid a stack overflow in a recursive algorithm?

Question What are the possible ways to solve a stack overflow caused by an recursive algorithm? Example I'm trying to solve Project Euler problem 14 and decided to try it with a recursive ...
26
votes
8answers
5k views

Are functional languages better at recursion?

TL;DR : Do functional languages handle recursion better than non-functional ones? I am currently reading Code Complete 2. At some point in the book, the author warns us about recursion. He says it ...
19
votes
2answers
1k views

Y combinator and tail call optimizations

The definition of a Y combinator in F# is let rec y f x = f (y f) x f expects to have as a first argument some continuation for the recursive subproblems. Using the y f as a continuation, we see ...
18
votes
10answers
9k views

What is so difficult about pointers/recursion? [closed]

In the perils of java schools Joel discusses his experience at Penn and the difficulty of "segmentation faults". He says [segfaults are difficult until you] "take a deep breath and really try ...
18
votes
7answers
5k views

What imperative programming languages do not support recursion?

To my knowledge, all modern imperative programming languages support recursion in the sense that a procedure can call itself. This was not always the case, but I cannot find any hard facts with a ...
17
votes
9answers
9k views

How do I explain “Recursion” to a 8 years old kid? [duplicate]

Possible Duplicate: In plain English, what is recursion? What is the best way to explain "Recursion" to 8 years old kid? I tried with the Fibonacci Series but i failed.
17
votes
5answers
10k views

Performance: recursion vs. iteration in Javascript

I have read recently some articles (e.g. http://dailyjs.com/2012/09/14/functional-programming/) about the functional aspects of Javascript and the relationship between Scheme and Javascript (the ...
15
votes
3answers
3k views

How many are too many nested function calls?

Quoted from MSDN about StackOverflowException: The exception that is thrown when the execution stack overflows because it contains too many nested method calls. Too many is pretty vague here. ...
15
votes
6answers
4k views

How do I determine the runtime of a double recursive function?

Given any arbitrarily double-recursive function, how would one calculate its run time? For Example (in pseudocode): int a(int x){ if (x < = 0) return 1010; else return b(x-1) + ...
14
votes
7answers
2k views

Why don't more languages support recursive/nested comments? [duplicate]

Possible Duplicate: Why do most programming languages not nest block comments? Most languages I've worked with don't have support for recursive/nested comments. Is there any reason why ...
12
votes
2answers
1k views

Can and do compilers convert recursive logic to equivalent non-recursive logic?

I've been learning F# and it's starting to influence how I think when I'm programming C#. To that end, I have been using recursion when I feel the result improves readability and I can't envision it ...
12
votes
2answers
12k views

Understanding Backtracking in C++

I have a good basic understanding of the fundamentals of C++, I also have an understanding of how recursion works too. I came across certain problems like the classic eight queens problem and solving ...
11
votes
7answers
2k views

Recursion — is it “divide and conquer” or “code reuse”

Recursion -- as we all know -- is one of those problems -- that wrapping your head around feels like achieving a "milestone" in your programming voyage. But when it comes to actually using it in ...
11
votes
3answers
343 views

Why does the iterative version take longer?

I was looking over at http://programming.lispdream.com/blog/2011/06/recursion-vs-iteration/ and I saw that on his implementation of the recursive and iterative implementations of the factorial ...
10
votes
9answers
2k views

Resources for improving your comprehension of recursion? [closed]

I know what recursion is (when a patten reoccurs within itself, typically a function that calls itself on one of its lines, after a breakout conditional... right?), and I can understand recursive ...
9
votes
7answers
15k views

Can a recursive function have iterations/loops?

I've been studying about recursive functions, and apparently, they're functions that call themselves, and don't use iterations/loops (otherwise it wouldn't be a recursive function). However, while ...
9
votes
2answers
12k views

Reason for return statement in recursive function call

I just had a doubt in my mind. The following subroutine(to search an element, in a list, for example) has a return statement at the end: list *search_list(list *l, item_type x) { if (l == NULL) ...
9
votes
2answers
1k views

Can someone explain the concept behind Haskell's memoization?

(note I'm putting the question here because it's about the conceptual mechanics of it, rather than a coding problem) I was working on a small program, that was using a sequence of fibonacci numbers ...
8
votes
4answers
1k views

When there's no TCO, when to worry about blowing the stack?

Every single time there's a discussion about a new programming language targetting the JVM, there are inevitably people saying things like: "The JVM doesn't support tail-call optimization, so I ...
8
votes
1answer
157 views

Finding all possible ways of inserting a pattern into a string

I've been thinking about this problem for a while, and I can only find a recursive solution but I'm feeling that there is a dynamic programming way to do it, I just can't figure it out. Is this a ...
7
votes
7answers
2k views

Is recursion an instance of being “too clever” when programming?

I've read several books and learned through experience that optimizing code to the point where it is inscrutable, or coming up with an extremely fast but extremely complex solution to a problem is not ...
7
votes
3answers
357 views

What would be a good approach to generate a tree of folders?

Say I have an array of strings, like this: var folders = new[] { "Foo", "Bar", "Foo\Bar" "Foo\Bar\Baz" }; And that I have an object that represents a folder - something like this: ...
7
votes
1answer
343 views

Process arbitrarily large lists without explicit recursion or abstract list functions?

This is one of the bonus questions in my assignment. The specific questions is to see the input list as a set and output all subsets of it in a list. We can only use cons, first, rest, empty?, empty, ...
6
votes
5answers
3k views

Can all the recursive functions be coded with iterations? [closed]

What are the advantages of recursion? Some programming languages can optimize tail recursion, but, still in general terms, recursion consume more resources than regular loops. Is it possible to ...
6
votes
4answers
350 views

How to convert the following node evaluation procedure to a non recursive solution?

I have the following recursive method. It evaluates a node (that represent a logical expression), using deep first search traversal : EvaluateNode(Node node) { bool result; switch(node.Type) ...
5
votes
10answers
5k views

In term of performance : while , for … Loops VS recursion [closed]

What is better for performance to write the loop as linear e.g. for , while or write it as recursion ?
5
votes
5answers
3k views

What is the difference between “recursion” and “self-reference”?

The wikipedia articles are too advanced for me to understand, could someone give me a simple explanation please?
5
votes
1answer
9k views

What does “recursive” mean for a program which processes files and directories?

I know what recursion is in programming. I do understand the basics of version control systems (have used svn that is). But I have often wondered what the meaning of "recursion" or "recursive" is ...
5
votes
2answers
1k views

Writing recursive functions

I am having a lot of trouble writing recursive functions related to trees. I can't just use google for these functions as they are not general and I won't be able to use google in an exam setting! Is ...
5
votes
3answers
483 views

How can I best study a problem to determine whether recursion can/should be used?

In some cases, I fail to see that a problem could be solved by the divide and conquer method. To give a specific example, when studying the find max sub-array problem, my first approach is to brute ...
5
votes
1answer
597 views

Is this an example of recursion?

I am implementing inheritance of something called Contexts. Each Context holds a link to its parent context. If that Context is the root Context, its parent is null. In order to walk up the ...
5
votes
3answers
3k views

Local Stack vs Call Stack

On the matter of Recursion: When you create a recursive function, you create a call stack. Ok, no problem; However, a comment on this page (look for comments by "LKM") triggered my curiosity (and ...
5
votes
4answers
1k views

Does the Composite design pattern implement recursive behavior?

The Composite design pattern allows us to call an operation() on a 'composite' node in a tree structure, and this operation() will be called on all of the children, subchildren and so on. When an ...
5
votes
1answer
282 views

Best way to deal with Floors and Ceiling when using substitution method to solve Recurrences

I'm currently using substitution method to solve recurrences. The problem I'm having is dealing with T(n) that have either ceilings or floors. For example in the following example see example here. ...
5
votes
0answers
98 views

Algorithm to generate all sets of m points in n x n x n cubic lattice which are unique under symmetry

I am implementing an algorithm which is going to be quite computationally complex, and want to try to make sure I'm not doing unnecessary work. There is an n x n x n cubic lattice, e.g. if n=2 this ...
4
votes
1answer
420 views

Why does `length - 2` recursively give you the center of a linked list?

I am reading through an Algorithms book and am working through a recursive solution to the following question: Implement a function to check if a linked list is a palindrome This is an easy ...
4
votes
4answers
5k views

Is there a way to display the stack during recursion method?

I'm trying to learn recursion. I copied this bit of code from my book and added the displays to help me trace what the method is doing and when. public static void main(String[] args) { ...
4
votes
3answers
7k views

Are there advantages for using recursion over iteration - other than sometimes readability and elegance? [duplicate]

I am about to make two assumptions. Please correct me if they're wrong: There isn't a recursive algorithm without an iterative equivalent. Iteration is always cheaper performance-wise than recursion ...
4
votes
3answers
737 views

Equal Gifts Algorithm Problem

Problem Link - http://opc.iarcs.org.in/index.php/problems/EQGIFTS It is Lavanya's birthday and several families have been invited for the birthday party. As is customary, all of them have brought ...
4
votes
7answers
1k views

How do i speedily traverse a file system while extracting/extrapolating various data and provide user feedback?

I'm working on a system file scanner that reveals info about various files (e.g. size, last used, duplicates, etc). Currently I'm traversing the file system once just to get a good measure of the ...
4
votes
1answer
3k views

Tips for Tail Call Recursion in Python [duplicate]

Ok, Python doesn't have tail call optimization. But for those who think better recursively than "looply", whats the best practices to write code?? 1000 stack calls are enough for many cases, but ...
4
votes
2answers
5k views

How do you work with Asynchronous functions, recursively?

I am currently working on FLEX and have to call a web services. once I have the result, I have to call the web service again, with the previous result as the input. A compounding problem, is that ...
4
votes
2answers
415 views

Is this the right strategy to convert an in-level order binary tree to a doubly linked list?

So I recently came across this question - Make a function that converts a in-level-order binary tree into a doubly linked list. Apparently, it's a common interview question. This is the strategy I ...
3
votes
4answers
3k views

Can recursion be done in parallel? Would that make sense?

Say, I am using a simple recursive algo for fibonacci , which would be executed as: fib(5) -> fib(4)+fib(3) | | fib(3)+fib(2)| fib(2)+fib(1) and so on ...