Questions tagged [recursion]
Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.
580
questions
0
votes
0
answers
587
views
Understanding Dynamic Programming through this example
I have trouble understanding The classic Mailbox Manufacturers Problem. You can read it here: https://open.kattis.com/problems/mailbox I have also found a solution text: http://www.ida.liu.se/projects/...
0
votes
0
answers
141
views
Recursive algorithm for counting pairs of ancestor and child, where sum =n
Hey, this is a question from my handouts, but how would I go about writing a recursive program that would return the number of pairs of an ancestor and a child, whose sum equals to n, given that the ...
- 185
0
votes
1
answer
895
views
How solve this recurrence: T(n) = 2t(n-1) - t(n-2) +5n +7 [duplicate]
I am trying to solve the recurrence: T(n) = 2t(n-1) - t(n-2) +5n +7 but without success.
And from here I don't know how to continue?
- 1
0
votes
0
answers
277
views
Iteration vs. recursion: what do these terms really mean?
Most of us know the typical answer to this question: if a function calls itself, it's recursion, if it's a loop, it's iteration. We also know that recursion can be simulated using iteration (by ...
0
votes
0
answers
50
views
time complexity question
I am reading a free algorithms textbook http://www.cse.iitd.ernet.in/~Naveen/courses/CSL630/all.pdf
and on page 13 i am stuck on an example they give.
"At this time, the fastest computer in the ...
- 41
0
votes
0
answers
16
views
How to solve this recursive relation T(n)= 2T(n/2) + 3T(n/5) +n [duplicate]
I don't think I'm able to solve this using the master's theorem, and solving separately doesn't seem to make sense. How does one go about solving this recursive relation?
T(n)= 2T(n/2) + 3T(n/5) +n
- 131
0
votes
0
answers
537
views
How to calculate the depth of the call stack for the average case of quicksort
In the best case of quicksort the depth of the call stack is measured by $\lceil\log_2 n\rceil$ if I am not wrong. What would be the formula for calculating the depth of the call stack in case of an ...
- 215
2
votes
2
answers
2k
views
Why are unbalanced partitions worse than balanced partitions in Quicksort?
I am unable to understand why unbalanced partitions in quicksort is actually worse than balanced partitions.
After reading this document it shows that worse case partitions are of the type $(0,(n-1)),...
- 215
1
vote
2
answers
682
views
Confusion over the complexity of parameter passing in merge sort
I'm working through CLRS on problem 4-2, which says the following:
Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an $N$-element array is ...
- 59
1
vote
0
answers
29
views
Creating a self-affine fractal on L-systems
Hi I would like to create a self-affine fractal on L-Systems.
The axiom I have created is FF-GGG-GG-GGG++GGG+GG-GGG+GG+GGG+FF++ffGG+GGG+FF+GGG which creates the image below
At each stage I would like ...
- 11
4
votes
1
answer
4k
views
Recursion Davis' Staircase understanding
I'm going through a hackerrank challenge on recursion https://www.hackerrank.com/challenges/ctci-recursive-staircase
and I'm having difficulty understanding how the solution below solves the problem. ...
- 41
3
votes
1
answer
380
views
what are Structural recursion, primitive recursion, recursion combinator and recursion principles?
Recently, I encountered terminologies such as primitive recursion and recursion combinator. One of the sources is here link
I googled and read some, but missing the points of them. I know that ...
- 1,062
2
votes
0
answers
206
views
Recursive definitions, How it is done?
I read that recursive definitions, refer to the definition of a function in that function body, cannot be done in $\lambda$-calculus, but recursion can be achieved by using $Y$ combinator.
As I know, ...
- 1,062
2
votes
2
answers
118
views
Find X contiguous segments in a range of integers
I've been struggling with the following problem: how do I find all possible sub-ranges in a range of integers where each segment is at least length 1, and I specify the total number of segments? A ...
- 121
2
votes
1
answer
329
views
Rod Cutting without using dynamic approach
Question
I want to Implement Rod cutting Algorithm without Dynamic Programming Approach.
Let me Describe the problem statement.
Given a rod of length $n$ inches and a table of prices $p_{i}$ for $...
- 317
1
vote
1
answer
1k
views
Space and time complexity of balanced parentheses enumeration algorithm
Consider the following recursive algorithm for printing all balanced strings with $n$ left and right parentheses. It is called with prefix = $\epsilon$ (the empty string):
A(prefix):
If prefix ...
- 11
2
votes
1
answer
5k
views
How can I convert a for loop to a recursive function?
My loop is pretty simple. The function takes in two parameters, a and b; both are integers where a<=b. The function will then create a list of numbers from a to b.
This is what I created:
...
- 21
1
vote
0
answers
759
views
Why is A* considered as a recursive search algorithm? [closed]
I'm currently studying informed search algorithms.
I've found a paper telling that A* is a recursive algorithm but I can't see where's the recursion part of this algorithm.
Why is A* considered as ...
- 111
0
votes
1
answer
372
views
$f:\Bbb N\dashrightarrow\Bbb N$ is partial recursive $\Leftrightarrow$ its graph is a recursively enumerable? [closed]
I have known that:
A function $\Bbb N → \Bbb N$ is recursive if and only if its graph is a recursive subset of $\Bbb N^2$.
Now I am considering about the partial functions. Is it the fact that:
...
- 133
4
votes
1
answer
262
views
Why is it that if we assume the Church-Turing thesis to be true, then human language must be recursive if the brain is finite?
I was reading "Why Only Us" by Chomsky and Berwick, and it said:
If one subscribes to the Church-Turing thesis along with the
assumption that the brain is finite, then there is no way out: we
...
- 2,960
2
votes
1
answer
91
views
Turning generative recursion results (leaves of a tree) into connected components (where each neighbour differs by one element)
I'm generating valid timetables for my uni with a simple generative recursion algorithm like this (disregarding handling of course-specific labs and tutorials)
...
- 208
0
votes
0
answers
144
views
Finding islands recursively in a matrix [duplicate]
I had this question in an interview recently. I was unable to answer this question and would really like to start a discussion on how to approach this problem and get the most efficient solution.
You ...
3
votes
2
answers
1k
views
How to solve the recurrence: T(n) = n*T(n-1) + n?
In a an exercise I'm required to analyze the runtime of recursive function:
...
- 351
9
votes
2
answers
2k
views
Correct name for a recursive descent parser that uses loops to handle left recursion?
This grammar is left recursive:
...
- 91
1
vote
0
answers
872
views
Why do we count the ceils and floors in recursive functions?
When we solve the recursive functions using substitution method, the impact of ceil and floor functions is trivial when the size of the input is large enough. For example the answer of
$$
T(n) = T(\...
- 1,509
0
votes
0
answers
20
views
The 0-1 Knapsack problem - Regression equation [duplicate]
I'm trying to figure out the regression equation for the 0-1 Knapsack problem recursive algorithm:
...
- 111
2
votes
1
answer
1k
views
A better upper bound to a recursive function
it's my first answer here.
I do have an algorithm to calculate the factorial of a given number $n$ recursively, but without using any multiplication like the usual one, only sums are available.
I'...
- 121
-1
votes
1
answer
3k
views
2
votes
0
answers
215
views
Maximum Move in a maze
Given a N * N maze, and string of N,E,W,S denoting positions to move to. I need to determine how many moves are possible in sequence out of a string (containing these 4 letters only) from each cell as ...
- 21
0
votes
0
answers
44
views
Recursive algorithm. Complexity [duplicate]
I need your help with time complexity.
I have this recursive function:
$$
F(n) = \left\{
\begin{array}{l l}
F(n-2) + 10 F\big(\frac{n}{6}\big)^2 + 6 F\big(\frac{n}{7}\big) + \frac{n^4}{5} & \...
- 1
0
votes
0
answers
530
views
Stack depth and initial call
I've not been able to find a precise definition of "stack depth" anywhere and have a rather simple question.
When dealing with trees I'm used to the maximum depth (or height) of the tree being the ...
- 323
0
votes
0
answers
173
views
Finding the shortest tour of a Pyramidal traveling salesman problem
We have a directed graph $G=(V,A)$ with $V=\{1,2,...,n\}$ where for each $(i,j)$ the distance $l(i,j)\in A$ is known. We want to find a pyramidal tour that has minimal length and that includes all ...
2
votes
2
answers
320
views
Converting $\beta$-bit integer to a decimal representation in $\Theta(M(\beta) \log \beta)$
The following problem is from CLRS (31.1-13, Page 933, 3rd edition):
Give an efficient algorithm to convert a given $\beta$-bit (binary) integer to a decimal representation. Argue that if ...
- 9,461
0
votes
0
answers
42
views
what will be the time complexity of below recursive algorithm [duplicate]
Please help me find the time-complexity of below recursive algo. I have guessed for first two return statements.Please correct me if I am wrong. But I can't find time-complexity of third return ...
- 1
2
votes
1
answer
116
views
Decimal to Binary converter with a flaw
Hi I wrote the following recursive decimal to binary function while studying for Andela.
...
- 123
1
vote
1
answer
62
views
Can such an algorithm be written using recursion
I'm writing an algorithm that, given a limit N, and given a list of elements of value V, find all the possible combinations so ...
user67642
1
vote
0
answers
879
views
What is a "pure recursive approach" [closed]
I am working on a homework assignment to create a function and it says to use a "pure recursive approach". I am trying to piece together what is actually meant by this. I am aware a recursive function ...
- 111
1
vote
2
answers
3k
views
Recursive algorithm - a^(2^n) [closed]
The a^n was pretty easy:
function powN(a, n) {
if(n == 0) return 1;
return a * powN(a, n - 1);
};
But somehow I got ...
- 27
3
votes
2
answers
11k
views
Time complexity of recursive power code
While I was learning about time complexity of recursive functions, I came across this code to calculate $x^n$:
...
1
vote
1
answer
222
views
Finding Permutations with Exclusions
Recently, I was given a puzzle by a friend of mine, which has 6 pieces. Giddy to try it out, I took it apart without batting an eye to follow what I was removing or moving or sliding.
I've been ...
- 125
0
votes
1
answer
172
views
Formulating a recursion using mathematical notation [closed]
So I'm assigned a task that involves formulating a quite complex recursion of several variables using 'mathematical notation'. The assignment is quite sparse when it comes to additional information, ...
- 265
5
votes
1
answer
657
views
Counting Total Number of Non-Equivalent Configurations in a 2-D Grid
This is a challenging question I've been trying (unsuccessfully) to solve via programming, math or both.
Suppose you're given a 2D grid, whose width and height, $w$ and $h$, can each range from $1$ ...
- 463
0
votes
1
answer
37
views
Evaluating tree data iteratively
Community,
I'm working on a project lifting assembler code to a AbstractSyntaxTree-like structures like these:
In order to be able to evaluate the final value of a tree given only leafes with ...
- 101
6
votes
1
answer
1k
views
Confused between turing-completeness and universal approximation - are they related?
I am trying to de-knot a point of confusion in my mind regarding "turing-completeness" and the "universal approximation theorem".
The context here is deep neural nets: So, consider two types of ...
- 161
0
votes
0
answers
40
views
Finding time complexity of an algorithm [duplicate]
I am to find the time complexity of my algorithm and I found one method here.
However I am really not sure about it correctness thus I would like to check it.
There is my algorithm (N is a set (len(N) ...
- 101
-2
votes
1
answer
140
views
How do you convert this iterative code to recursive?
How do you convert the following algorithm from the iterative paradigm to the recursive paradigm?
Input: array $A[1],\ldots,A[n]$
Output: last index $i$ such that $A[i] = i$, or $-1$ if none
Algorithm:...
1
vote
1
answer
134
views
Complete $\mu$-recursive function that is not primitive recursive
Could you find an example of a complete $\mu$-recursive function that is not a primitive function?
- 83
2
votes
2
answers
115
views
Help with recursive algorithm analysis
Given this algorithm:
int foo(int num) {
if (num == 0){
return 0;
} else {
return 1 + foo(num/10);
}
}
Me and my friend are debating ...
- 351
4
votes
2
answers
403
views
What is a 'subrecursive algorithm'?
I am reading Exploring Robotic Minds by Prof. Jun Tani, and came across the term subrecursive. Original context:
Another possibility might be to assume ...
- 143
46
votes
5
answers
12k
views
Iteration can replace Recursion?
I've been seeing all over stack Overflow, e.g here, here, here, here, here and some others I don't care to mention, that "any program that uses recursion can be converted to a program using only ...
- 1,607