The recursion tag has no usage guidance.
0
votes
1answer
66 views
Why isn't this combinatorial solution equivalent to the recursive solution for finding the number of “paths”?
Here's the problem:
Given an m x n array, get the number of different paths from the top left corner to the bottom right corner, if you can only move down, right, and diagonally down & right.
...
2
votes
4answers
1k views
Why does recursion return the first call in the stack and not the last?
I cant for the life of me figure out why this returns 0 rather than 5. i keeps getting incremented before it hits the last return statement, however it always returns 0, from the first call in the ...
-3
votes
1answer
91 views
Python recursion in functions [closed]
I am just learning about recursive functions. This was an example given in a textbook where t is a turtle. I was wondering how the code works, but more specifically, how the code runs past the first ...
4
votes
1answer
211 views
How does K&R's qsort work?
In the recursion section of K&R's ANSI C book, they demonstrate a
version of quicksort [that] is not the fastest possible, but it's one of the simplest.
--The C Programming Language (ANSI ...
0
votes
2answers
160 views
How to decide how to build a recursive function
Sometimes when you're coding you're on a problem which can be solved with some recursive method. What is for you the best way to detect when the recursion is a good way to solve a problem and how to ...
2
votes
2answers
122 views
Designing the recursive solution
I understand the recursion and find it useful and intuitive while solving problems on trees but for many other problems recursion never fails me to leave puzzled. Recently I was solving the following ...
3
votes
1answer
250 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 (...
0
votes
1answer
152 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
0answers
59 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 ...
34
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 ...
3
votes
3answers
177 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-...
1
vote
1answer
107 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 ...
2
votes
5answers
363 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
51 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
129 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 ...
0
votes
2answers
108 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 ...
1
vote
0answers
69 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 possible ...
1
vote
1answer
119 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
25 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
102 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
169 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 ...
1
vote
1answer
158 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(...
8
votes
1answer
264 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 ...
8
votes
1answer
210 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
148 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
112 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
376 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
172 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
226 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 ...
116
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
223 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 a ...
3
votes
2answers
244 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
55 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
446 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 enough ...
0
votes
2answers
246 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
802 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
4k 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
241 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
164 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
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^...
2
votes
2answers
262 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
124 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 ...
2
votes
1answer
485 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 ...
11
votes
1answer
7k 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 ...
0
votes
2answers
139 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 :...
1
vote
3answers
467 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
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)
...
0
votes
2answers
146 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
128 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 ...
