The recursion tag has no usage guidance.
3
votes
1answer
58 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 ...
1
vote
1answer
142 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 ...
5
votes
0answers
61 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 ...
7
votes
1answer
148 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 ...
2
votes
1answer
125 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 ...
-1
votes
1answer
104 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
354 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
91 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
170 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 ...
109
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 ...
0
votes
3answers
164 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 ...
3
votes
2answers
187 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.
1
vote
0answers
46 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,
...
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 ...
0
votes
2answers
138 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 ...
3
votes
4answers
522 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
1k 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
208 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
105 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
0answers
33 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 ...
2
votes
2answers
183 views
Why left recursion not looping?
I'm trying to read the parser of PHP, that says:
top_statement_list:
top_statement_list top_statement
| /* empty */
;
It is a left-recursion, but why it don't looping infinitely?
My ...
0
votes
1answer
105 views
Recursion, iteration, and …? [closed]
Here are three common code structures that apply a function multiple times:
foo(x) {
if basecase(x) return k else return foo(g(x))
}
uses recursion.
for i in 0..10 {
n *= bar(i)
}
uses ...
1
vote
1answer
335 views
What are the time and space complexities of this recursive method that reverses a singly linked list?
What are the Time and Space complexities of this Java method that reverses a singly linked list (of length n)?
I'm more interested in knowing the reasoning behind the space complexity. Let me know if ...
0
votes
0answers
84 views
Software paradigms: prove that sum and sum1 are equal
Here are given two functions that calculate the sum of elements in a list. The proof should be done using induction.
The hypothesis is: sum(as) = sum1(as, 0)
def sum( as : List [ Int ] ) : Int = as ...
2
votes
1answer
2k 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 acedemic;)
The example is offering a thought, I wanna a generic way, so example is only used as to make us more ...
0
votes
2answers
112 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
0answers
40 views
build list of possible permutations with dynamic set size
I'm trying to develop code/pseudocode to build a list of all permutations given the following data. I'm developing in a java-like language for a web app. I don't have any java libraries for this ...
1
vote
3answers
340 views
Check distance between all elements in a list of numbers in O(n*lg(n))
I have an exercise for my algorithms and data structures class, where I basically have to implement a divide and conquer algorithm or function called check_distance to determine whether all numbers in ...
3
votes
4answers
1k 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)
...
0
votes
2answers
131 views
Trouble understanding simple recursion in c [duplicate]
My function:
int num(int x)
{
if(x>0)
num(x-1);
else
return 0;
printf("%d",x);
}
This function takes a input x and prints the numbers from 1 upto x.I can't seem to ...
1
vote
1answer
116 views
Why does this recursion method work? I have explored it for a day or two, and I cannot figure out why
Problem Statement:
I have a tree with node values ( i , j ) where i , j < 1. The children of each node take on the values (i - 1, j), (i - 1, j - 1), and (i, j - 1) respectively. Now, i and j have ...
3
votes
2answers
157 views
Is there a (systematic) way to convert a recursive program to a version using user stack?
I have an image (an array of 1000 x 1000 pixels) of 1s and 0s. I was asked to do edge detection, so I wrote this program in C to traverse the figure. My idea was to convert every pixel surrounded by ...
0
votes
2answers
385 views
Is recursion a declarative approach to solve the problems?
I have noticed many problems in algorithms textbook are solved by recursion (divide and conquer, backtracking,...)
As I tried to enhance my skills in writing them, I have noticed, I just need to ...
41
votes
4answers
11k 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 ...
0
votes
2answers
135 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) ...
6
votes
4answers
338 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)
...
0
votes
1answer
97 views
Handling the process of large-scale lists [closed]
What are the efficient ways to process huge lists (+10 millions), and things to consider while manipulating huge lists.
First question, when should I use recursion, and when I shouldn't. In both ...
1
vote
1answer
399 views
Is it possible to apply Master Theorem for finding the square and cube root
I was asked to calculate the running time of an algorithm which finds the square root and cube root of a given number.
Is it possible to apply Master theorem with regards to this? First, I need to ...
2
votes
1answer
1k views
how to enumerate/generate all possible binary trees from N leaves and N-1 nodes?
I am trying to implement the 24 Game in ansi C. This game goes as follows:
For a list of four given numbers, try to find a solution involving these four numbers, that, using addition(+), ...
2
votes
1answer
357 views
Do compilers un-inline recurrent expressions?
Does a compiler look for recurrent expressions to convert it into 'function' to reduce binary size and improve performance?
Of course, the obvious answer might be "some do it, some don't", so I ask ...
3
votes
3answers
8k 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 ...
2
votes
1answer
205 views
How to efficiently sort a recursively defined Stack?
I am trying to implement a recursively defined Stack and sort it in Java.
I don't have a particular usage of this program in mind. I found this approach of stack implementation a bit useful while ...
3
votes
4answers
209 views
Wrap all external calls with flag to fight against recursion and double-entry?
Producing predictable output for each possible input is the responsibility of each module. For example (in C#):
class Logger
{
public ITextWriter Writer { get; set; }
private uint counter;
...
0
votes
3answers
205 views
What does this function do?
Does this function means its calculating x=(x-1) + x^2?
Function unknown(x)
if ( x == 1 )
return 1
else
return unknown(x‐1) + x*x
5
votes
1answer
279 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.
...
2
votes
2answers
183 views
Is this looping solution possible with recursion?
Eventually, I would like to generalize this solutions to work with a Tuple of any length. I think recursion is required for that, but I haven't been able to do it.
def combineRanges(maxValues) :
...
0
votes
3answers
323 views
How to convert this recursive problem to iterative? Line Simplification algorithm fails to run due to Maximum Recursion Depth being hit
I am implementing the Douglas, Peucker's Line Simplification algorithm in Python. I started with this implementation. However, it fails to run in Python due to Maximum Recursion Depth being hit. How ...
2
votes
2answers
159 views
General recursion to tail-recursion
Is it theoretically possible to transform every kind of general-recursion into tail-recursion? Are they equivalent for example from a lambda-calculus point of view? That's a debate between me and an ...
2
votes
2answers
305 views
Calling same method on different object - Recursion?
I have an object that contains a reference to another object of the same type. Example in PHP:
class A {
protected $child;
public function __construct(A $child = null) {
...
3
votes
1answer
380 views
How can I rewrite this linked-list manipulation as tail-recursive?
Given a liked list, I'd like to swap every pair of nodes as follows:
input: a-b-c-d-e-f-g
output: b-a-d-c-f-e-g
If there's an odd number of nodes then the last node is tacked on as-is. This should ...
