# Questions tagged [recursion]

Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.

580 questions
Filter by
Sorted by
Tagged with
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/...
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
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?
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 ...
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
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
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
2k views

• 317
1 vote
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
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
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
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
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
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
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 ...
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
2k views

### Correct name for a recursive descent parser that uses loops to handle left recursion?

This grammar is left recursive: ...
1 vote
872 views

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 ...
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 ...
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
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 ...
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
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 ...
1 vote
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 ...
1 vote
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 ...
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
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
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
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
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
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
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
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
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
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
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