# Questions tagged [recursion]

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

373 questions
Filter by
Sorted by
Tagged with
878 views

699 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 ...
1k 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: ...
216 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 ...
182 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: ...
192 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 ...
66 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) ...
71 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 ...
682 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: ...
973 views

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

This grammar is left recursive: ...
324 views

213 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 ...
151 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 ...
178 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 ...
90 views

### Decimal to Binary converter with a flaw

Hi I wrote the following recursive decimal to binary function while studying for Andela. ...
58 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 ...
458 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 ...
1k 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 ...
5k 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$: ...
146 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 ...
128 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, ...
376 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$ ...
34 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 ...
490 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 ...
39 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) ...
96 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 ...
106 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?
105 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 ...
234 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 ...
9k 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 ...
162 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 \...
585 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$....
6k 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. ...
435 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 ...