# Questions tagged [recursion]

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

424 questions
Filter by
Sorted by
Tagged with
340 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 ...
1k views

829 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 ...
2k 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: ...
366 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 ...
211 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: ...
206 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 ...
68 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) ...
81 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 ...
953 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: ...
1k views

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

This grammar is left recursive: ...
422 views

370 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 ...
159 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 ...
253 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 ...
41 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 ...
92 views

### Decimal to Binary converter with a flaw

Hi I wrote the following recursive decimal to binary function while studying for Andela. ...
59 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 ...
544 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 ...
2k 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 ...
7k 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$: ...
177 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 ...
138 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, ...
424 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$ ...
35 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 ...
566 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 ...
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 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,\ldots,A[n]$ Output: last index $i$ such that $A[i] = i$, or $-1$ if none Algorithm:...
112 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?
106 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 ...
266 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 ...
10k 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 ...
165 views

### Solving recurrence $T_k(n) = T_k\left(\left \lfloor \frac{n}{2} \right \rfloor\right) + T_k\left(\left \lceil \frac{n}{2} \right \rceil\right)$

I am currently solving a problem that I have reduced to computing the following function efficiently. T_k(n) = T_k\left(\left \lfloor \frac{n}{2} \right \rfloor\right) + T_k\left(\left \lceil \...
592 views

### Running time of greedy scheduling algorithm

Here is an algorithm to output a subset of activities S such that no activities in S overlap and profit(S) is maximum. Define $p[i]$ to be the largest index $j$ such that $a_j$ does not overlap $a_i$....
7k views

### Converting recursive algorithm to DP

As a follow-up to this question , I've found a recursive algorithm that solves the given problem, but it runs too slow to pass all given tests. ...
442 views

### Computing the minimal flexible distance of two vectors using dynamic programming

I can't figure out a recurrence equation for a dynamic programming assignment. Formally, we aim to minimize the total sum of distances between matched points with the following constraints: Every ...