The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
1answer
79 views

how is stack and heap are assigned to each processes?

How multiples processes are stored in the main memory , i understand every process will be divided into the equal size pages and will be stored in the frames of main memory. if whole main memory is ...
1
vote
1answer
207 views

Are recursions intrinsically less safe than iterations?

Java doesn't have a predefined recursion depth limit. As a result the recursion below (a dummy method that returns the value) throws java.lang.StackOverflowError after 62844 (with static) and 14002 (...
10
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 ...
28
votes
11answers
8k views

Is a while loop intrinsically a recursion?

I wondered whether a while loop is intrinsically a recursion? I think it is because a while loop can be seen as a function that calls itself at the end. If it is not recursion, then what is the ...
0
votes
0answers
21 views

Algorithm to generate all paths between two vertices of a graph in F#

Following a functional programming approach (no mutable data structures, recursion, etc) I have written a script in F# to generate all paths between two vertices of an undirected, unweighted graph. I ...
7
votes
1answer
4k views

General way to convert a loop (while/for) to recursion or from a recursion to a loop?

This problem is mainly focusing on the algorithm, maybe something abstract and more academic. The example is offering a thought, I wanna a generic way, so example is only used as to make us more ...
-2
votes
0answers
20 views

Minimum value of a node in a binary search tree

I am making a program that returns the minimum value of a binary search tree recursively and I don't know how to implement it. I am stucked here, please help def bst_min(t): if t.is_leaf == True: ...
1
vote
1answer
55 views

Recursive interface implementation causes empty method

TLDR: I have a situation where interface implementations accept other implementations of that very interface. Only a subselection of these interface implementations should carry a certain method - but ...
0
votes
2answers
106 views

How to mentally keep track of recursion

I have great trouble doing recursion, especially trying to visualize it. A great example is the aging wine problem described in the top answer of this link: https://www.quora.com/Are-there-any-good-...
2
votes
5answers
278 views

Recursion in Merge Sort algorithm. How is it obvious to use this type of recursion?

I dont want to put too much code so I'll just put the code that involves recursion. This algorithm is fairly well known so I think everybody knows the basic code. void mergeSort(int array[], int l, ...
0
votes
1answer
44 views

Reflexive calls of objects in the same hierarchy

I am not sure how to phrase this. I believe this should have been asked somewhere, but I am unable to find it because I don't know the keywords. Basically, I have some types like this: interface Foo ...
-2
votes
1answer
119 views

How does this recursive function exit? [closed]

In the merge_sort part, there are multiple calls to the same function within the recursive. How are the other two executed when the definition holds that till a condition is false, the recursion does ...
5
votes
1answer
169 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 ...
0
votes
2answers
62 views

Implementing map with tail recursion

I am trying to solve this exercise. It is about reimplementing the map function in haskell for learning purpose. I found a solution which doesn't browse all the elements of the list (simple linked ...
8
votes
1answer
192 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 ...
1
vote
0answers
53 views

String Pattern Matching from Lookup Table - Non-Exponential Solution?

Given the problem... Given a String comprising of non-alhpabetical symbols, and a Lookup Table where a subset of those symbols may equate to a single alphabetical character, output all ...
3
votes
3answers
10k views

Find all possible subarrays of an Array

I am lost I just can't seem to get my head around backtracking/recursion approaches. I understand how simple recursion problems like factorials work I can even trace those by hand. But when it comes ...
5
votes
6answers
4k 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 Now,...
1
vote
1answer
109 views

Understanding recursive solution of some algorithm

Most of the time we need to understand someone else' code for example I am studying Graph Algorithms from Sedgewick's online resources, the particular code example is taken from cycle detection ...
0
votes
0answers
24 views

Reverse lookup of data based on user input

I have an array in the format: $array = array( 0 => array( 'name' => 'Item 1', 'level' => 1, 'points' => 10 ), 1 => array( 'name' => '...
0
votes
1answer
80 views

Achieving permutation using recursion [closed]

Though I like recursions and understand it, I fail to master it! I am stuck with a problem which I know that recursion can solve, but I do not know how. I have an array of strings like: "hundred", "...
-2
votes
1answer
163 views

For loop and recursion for a new shell in C [closed]

I code a new shell in C, that could be done in several ways: Flex/bison, finite state machine, abstract syntax tree or just a tokenizer in C. Now I've written a for-loop that changes the condition of ...
3
votes
1answer
83 views

Term for the current iteration of a recursive function call

Is there a standard or widely accepted term for referring to a variable within the current call of a recursive function where the last value of the same variable is passed as an argument? I am trying ...
3
votes
4answers
2k views

Robot in a grid

This was recently asked to someone I know. A robot has to move in a grid which is in the form of a matrix. It can go to A(i,j)--> A(i+j,j) (Down) A(i,j)--> A(i,i+j) (Right) ...
1
vote
1answer
153 views

Complexity of recursive calls

my brain is a little stuck as I am trying to compile an example for my blog. I am presenting an algorithm that draws a number from an array, adds it to a sum and calls itself recursively. func solve(...
2
votes
1answer
135 views

Enumerating the primitive recursive functions

How can I enumerate (by expression tree size, for example) all of the primitive recursive functions that map natural numbers to natural numbers in a traditional programming language like C? For ...
30
votes
8answers
26k 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 algorithm....
-1
votes
1answer
107 views

Problem on recursion

void function(int x){ if(x<=0) return; function(x--); } This is a recursion function which is called with the value of x = 20. The Recursive call will take place in this way ...
7
votes
3answers
363 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: ...
3
votes
3answers
131 views

What can qualify for potential tail call recursion (TCO) optimization or tail recursion elimination (TRE)

Short question is: what can qualify for potential tail call recursion optimization (TCO) or tail recursion elimination (TRE) if the compiler or interpreter supports it. The summary of this question ...
0
votes
1answer
188 views

False recursion vs. true recursion [closed]

I have been warned by my professor to avoid "false recursion", where a function behaves recursively, but does no useful recursive work. I believe I understand recursion, but would like to double ...
114
votes
11answers
13k 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 ...
0
votes
3answers
187 views

Is recursion a bad idea for large input sizes due to the limited call stack size? [duplicate]

Call stack size in JavaScript: Three results: - Node.js: 11034 - Firefox: 50994 - Chrome: 10402 It seems like it would be a bad idea to use recursion for things like BST insertion, because there's ...
43
votes
4answers
13k 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 ...
3
votes
2answers
207 views

What was the first language to support convenient user-land recursion?

What was the first programming language to support convenient user-land recursion? I know that early languages did not support it, but can find no specifics on when it was introduced.
17
votes
5answers
11k 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 ...
1
vote
0answers
49 views

Recursive(?) algorithm design help

I have a requirement to allow my end users to input formula much like a spreadsheet. I have an array like this: $table = array( 1=>array( "id"=>1, "Name"=>"...
4
votes
1answer
424 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 ...
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 ...
0
votes
2answers
179 views

A Python program that illustrates the tree-like structure of recursion [closed]

I want to write a program in Python that illustrates the tree-like feature of recursion, using the example of "fibo(n)" function. I wonder how to modify the following program: def fibo(n): if n==...
3
votes
4answers
618 views

Why can't I call a constructor in itself?

I am currently porting the class NumberRange from Java to C#. I am writing this constructor and I wonder whether I can call a constructor in itself. Something like this: public NumberRange(Double ...
1
vote
4answers
2k views

How does recursive backtracking work ?

I am trying to figure out recursive backtracking, i have good understanding of recursion and till some extent the concept of backtracking too but i am having difficulty understand the chronological ...
1
vote
1answer
221 views

Why do I need to use recursion on the classic employee manager database relationship?

Take the data from the Oracle scott database. I have modified it to have multiple levels of management from the original, select * from scott.emp order by mgr desc; empno ename job ...
2
votes
1answer
130 views

How to calculate number of indirect dependencies of a class?

Most of the static code analysis tools which analyse class dependencies generate dependency pairs of classes where each pair represents a direct dependency between two classes. Given those dependency ...
0
votes
2answers
124 views

Given a tree calculating Max Sum from top to bottom suing DFS? optimization?

given a tree i want to calculate max sum of each path from top to bottom. I used DFS for the operation. Here is the function which takes root as input and gives max sum of the path from top to bottom :...
0
votes
2answers
140 views

Time complexity analysis for recurrence relation

I was asked to figure out the time complexity analysis for the following recurrence relation T(n) = 4*T(n-1) + c. Basically, I did a replacement.. T(n-1) = 4 * T(n-2) + c and so on.. T(n) = 4^k T(1) ...
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 ...
0
votes
4answers
11k views

Finding the time complexity of the following program that uses recursion

I need to find the time complexity in terms of Big Oh notation for the following program which computes the factorial of a given number: The program goes like this: public int fact(int n){ if (n &...
0
votes
0answers
34 views

What's the bound of the following recurrence?

Given the following recurrence: T(n) = T(n-1) + n^2 How can I prove it to be O(n^3) with the substitution method? The O(n^3) guess derives from the fact that at every step of the recursion we pay n^...
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 ...