# Questions tagged [recursion]

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

423 questions
Filter by
Sorted by
Tagged with
138 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: <...
93 views

582 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 ...
179 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 ...
53 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 ...
461 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 ...
250 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.
127 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. ...
198 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 ...
684 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. ...
160 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 '...
337 views

### Why is recursive programming problematic for branch predictors

Consider for example the following recursive program: ...
89 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 ...
69 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 ...
654 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. ...
40 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 ...
328 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 ...
234 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 ...
197 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, ...
117 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. ...
3k views

### What is the time complexity of this binomial coefficient algorithm?

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$: ...
40 views

### 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 ...
367 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/...
128 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 ...
580 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?
211 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 ...
47 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 ...
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 ...