A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [recursion]

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

380 questions
Filter by
Sorted by
Tagged with
1k views

### Longest increasing subsequence (Dynamic Programming)

I have written the following recursive structure for finding length of longest increasing subsequence. ...
50 views

### The evolution of the term “recursive” from Goedel to Church to present day

I'm currently studying some of the history of computation / computability, in the early days known as recursion theory. I see Goedel's definition of recursive functions seems significant in his paper,...
352 views

### Making a recursive formula for finding amount of ways to spend money on beer

So far, i've only made recursive formulas for finding simple patterns such as fibonacci, however i can't seem to get my head around this. The information available is that there are $n$ different ...
150 views

### Alan Perlis Epigram on Recursion

So, while trying to dive into "recursion" and the like, I came across an epigram about recursion by Alan Perlis: Recursion is the root of computation since it trades description for time. -- ...
120 views

### Proving the correctness of a square summing algorithm

int sumHelper(int n, int a) { if (n==0) return a; else return sumHelper(n-1, a + n*n); } int sumSqr(int n) { return sumHelper(n, 0); } I am supposed ...
1k views

### How does in-order traversal in Binary search tree works (recursion)

I visit some question but their implementations are slightly different and my doubt is not like theirs. I have this code in Javascript. The code is typical BST implementation with methods to support ...
282 views

### Understanding Martin Farach's suffix tree algorithm

I feel stuck at this point. I have spent several days trying to get my head around the algorithm, but both resources I have   seems to skip over whatever details that would make me comfortable ...
123 views

### Proof of correctness recursive reverse digit function

This is an attempt to understand better recursion. The following recursive function returns the integer obtained by reversing the digits of an input integer. I'm trying to prove its correctness: <...
86 views

531 views

### Towers of Hanoi First Move

I've finally more or less understood the recursive algorithm for solving the Towers of Hanoi. My Python code is below. However one thing still bugs me - I can't yet work out how this simple seeming ...
154 views

### Ackerman hierarchy for higher order primitive recursion in System T

Gödel defines in his System T primitive recursion over higher types. I found notes from Girard where he explains the implementation of System T on top of simply typed lambda calculus. On page 50 he ...
61 views

### Is there any practical application for arrays that contain themselves?

I'm reading the introduction to Godel, Escher, Bach and and there's heavy discussion of mathematical sets which contain themselves. Being a far better programmer than mathematician, I put it into ...
49 views

### Integer log2 as a catamorphism?

Recursion schemes are structured methods for expressing recursive functions, of increasing interest due to their ubiquity in functional programming. For example, catamorphisms (familiar in the guise ...
412 views

### If all edges are unweighted AND DIRECTED, can one use BFS to obtain a MST?

I've looked through CS SE and I've found a page that said you could find use BFS to find a MST if the edges are unweighted, but what if the edges are directed? Given a directed graph between V ...
2k views

### Difference between Tail-Recursion and structural recursion

Is there any difference between structural-recursion and Tail-recursion or they both are same? I see that in both of these recursions , the recursive function is called on the subset of the orignal ...
232 views

### Is it beneficial to convert recursion to tail recursion? [duplicate]

If it is beneficial, then how Big-O (time complexity) is affected? Embedded link provided by members does not answer original question.
121 views

### Can we use recursion for large pool of input data? [closed]

While studying recursion, I came to know that for every function call it has to store intermediate data on stack for later use. If so, then for large amount of data, recursion can be inefficient. ...
168 views

### Towers of Hanoi Algorithm “Using Auxiliary” Peg

I'm trying to fully understand how the recursive Towers of Hanoi Algorithm works and to implement it in code. Something that keeps throwing me of is the use of phrases like "move n-1 discs from A to ...
573 views

### DP tiling a 2xN tile with L shaped tiles and 2x1 tiles?

https://www.iarcs.org.in/inoi/online-study-material/topics/dp-tiling.php The second question in the above link requires us to fill an 2xN grid with tiles of dimension 2x1 and an L shaped tile. ...
126 views

### Recursive definition of a language $L$ over $\{a,b\}$

How would I start the recursive definition of the following language: L over {a, b} such that L consists of strings in which each occurrence of b is immediately preceded and followed by an a The ...
267 views

### Why is recursive programming problematic for branch predictors

Consider for example the following recursive program: ...
86 views

### What is the run time of this algorithm?

Robot in a grid: Imagine a robot sitting on the upper left corner of a grid with $r$ rows and $c$ columns. The robot can only move in two directions, right or down, but certain cells are off limits ...
62 views

### Dynamic Programming Recursive Algorithm - Number of heads in a series

So I have this programming prompt which asks me to figure out how many permutations of a 32 coin toss sequence do not have three or more heads consecutively tossed. We are supposed to use Dynamic ...
571 views

### What property of cons allows elimination of tail recursion modulo cons?

I'm familiar with the idea of basic tail recursion elimination, where functions that return the direct result of a call to themselves can be rewritten as iterative loops. ...
31 views

### How is this defined in an iterative style?

This is the so-called recursive style: And this is the so-called iterative style: It seems like it is defined recursively to me. The function doesn't hide the next call of the function defined in it ...
322 views

### Find height of deepest FULL level in binary tree

Suppose I have a binary tree that is guaranteed to have at least one level that holds the maximum amount of nodes possible. I want to find the height of the deepest level that is full/holds the ...
209 views

### Understanding time complexity for kth minimum in CLRS

In chapter 10.3. Selection in worst - case linear time ($k$th minimum) from Introduction to Algorithms by Cormen, Leiserson and Rivest, the time complexity expected for step 5 of the algorithm ...
180 views

### How to convert this recursive algorithm to an iterative form?

Let us assume there's a folder structure as shown below: The letters a-d represent folders and the number 1-5 represent video files where for the file n, ...
110 views

### Converting Recursion into Into Iteration [duplicate]

While reading Code Complete second edition, I came across this line: You can do anything with stacks and iteration that you can do with recursion. Is this true? or there are functions, that must ...
20 views

### recursive function Time complexity [duplicate]

I studied this algorithm. Link. Is is about finding all possible binary trees with given inorder traversal. I want to analyze this code with Big-O notation. I think it is O(N^3). Below is my thought. ...
Here's a naïve algorithm that computes $\binom{n}k$ (or "n choose k"), with either $k=0$ or $1\le k \le n$: ...
### If $R(x,y)$ is a recursive relation, then $\exists y\leq 2$ such that $R(x,y)$ is recursive
The theorem says: If $R(x,y)$ is a recursive relation, then there exists $y\leq2$ such that $R(x,y)$ is recursive. Here is my attempt of proof: Since $R(x,y)$ is recursive, we can construct a ...