Questions tagged [recursion]

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

Filter by
Sorted by
Tagged with
76 votes
4 answers
72k views

What is tail recursion?

I know the general concept of recursion. I came across the concept of tail recursion while studying the quicksort algorithm. In this video of quick sort algorithm from MIT at 18:30 seconds the ...
Geek's user avatar
  • 1,181
46 votes
5 answers
12k 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 ...
Tobi Alafin's user avatar
  • 1,587
33 votes
6 answers
72k views

What is most efficient for GCD?

I know that Euclid’s algorithm is the best algorithm for getting the GCD (great common divisor) of a list of positive integers. But in practice you can code this algorithm in various ways. (In my case,...
Jonathan Prieto-Cubides's user avatar
26 votes
5 answers
46k views

When to use recursion?

When are some (relatively) basic (think first year college level CS student) instances when one would use recursion instead of just a loop?
Taylor Huston's user avatar
22 votes
2 answers
3k views

Recursive definitions over an inductive type with nested components

Consider an inductive type which has some recursive occurrences in a nested, but strictly positive location. For example, trees with finite branching with nodes using a generic list data structure to ...
Gilles 'SO- stop being evil''s user avatar
20 votes
3 answers
18k views

Why are loops faster than recursion?

In practice I understand that any recursion can be written as a loop (and vice versa(?)) and if we measure with actual computers we find that loops are faster than recursion for the same problem. But ...
Niklas Rosencrantz's user avatar
18 votes
3 answers
16k views

Can a tree be traversed without recursion, stack, or queue, and just a handful of pointers?

Half a decade ago I was sitting in a data structures class where the professor offered extra credit if anyone could traverse a tree without using recursion, a stack, queue, etc. (or any other similar ...
NL - Apologize to Monica's user avatar
17 votes
2 answers
1k views

Does the Y combinator contradict the Curry-Howard correspondence?

The Y combinator has the type $(a \rightarrow a) \rightarrow a$. By the Curry-Howard Correspondence, because the type $(a \rightarrow a) \rightarrow a$ is inhabited, it must correspond to a true ...
Joshua's user avatar
  • 273
15 votes
6 answers
4k views

Examples of sophisticated recursive algorithms

I was explaining the famous deterministic linear-time selection algorithm (median of medians algorithm) to a friend. The recursion in this algorithm (while being very simple) is quite sophisticated. ...
elektronaj's user avatar
15 votes
2 answers
1k 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. ...
Maxpm's user avatar
  • 253
14 votes
2 answers
4k views

Will this program terminate for every Integer?

In a Part Test for GATE Preparation there was a question : f(n): if n is even: f(n) = n/2 else f(n) = f(f(n-1)) I answered "It will terminate for all ...
Prakhar Londhe's user avatar
13 votes
4 answers
4k views

Why is tail recursion better than regular recursion?

There is the axiom you should always prefer tail-recursion over regular recursion whenever possible. (I'm not considering tabulation as an alternative in this question). I understand the idea by why ...
AmandaSai98b's user avatar
13 votes
4 answers
44k views

Complexity of recursive Fibonacci algorithm

Using the following recursive Fibonacci algorithm: def fib(n): if n==0: return 0 elif n==1 return 1 return (fib(n-1)+fib(n-2)) If I input ...
joker's user avatar
  • 461
13 votes
1 answer
4k views

Is this a generic way to convert any recursive procedure to tail-recursion?

It seems that I've found a generic way to convert any recursive procedure to tail-recursion: Define a helper sub-procedure with an extra "result" parameter. Apply what would be applied to the ...
nalzok's user avatar
  • 1,071
11 votes
2 answers
920 views

How to derive dependently typed eliminators?

In dependently-typed programming, there are two main ways of decomposing data and performing recursion: Dependent pattern matching: function definitions are given as multiple clauses. Unification ...
jmite's user avatar
  • 29.5k
11 votes
3 answers
879 views

Do "inductively" and "recursively" have very similar meanings?

Do "inductively" and "recursively" mean very similar? For example, if there is an algorithm that determines a n-dim vector by determine its first k+1 components based on its first k components having ...
Tim's user avatar
  • 4,785
11 votes
1 answer
2k views

Towers of Hanoi but with arbitrary initial and final configuration

Recently, I came across this problem, a variation of towers of hanoi. Problem statement: Consider the folowing variation of the well know problem Towers of Hanoi: We are given $n$ towers ...
Null's user avatar
  • 211
10 votes
3 answers
4k views

Algorithm to test whether a binary tree is a search tree and count complete branches

I need to create a recursive algorithm to see if a binary tree is a binary search tree as well as count how many complete branches are there (a parent node with both left and right children nodes) ...
OghmaOsiris's user avatar
9 votes
1 answer
540 views

What is the running time of this recursive algorithm?

I made the following (ungolfed) Haskell program for the code golf challenge of computing the first $n$ values of A229037. This is my proposed solution to compute the $n$th value: ...
Michael Klein's user avatar
8 votes
2 answers
3k 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 ...
Khan Saab's user avatar
  • 253
8 votes
2 answers
2k views

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

This grammar is left recursive: ...
user71015's user avatar
8 votes
4 answers
5k views

Teaching Recursion

I'm a teacher assistant in my university and my next topic is recursion. what way is the best to teach recursion so that the student can grasp the concept easily and can think recursively? I was ...
Amen's user avatar
  • 163
8 votes
4 answers
428 views

What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?

We have a function which takes an array as input. It breaks an array into $\log_2(n)$ parts with equal sizes where $n$ is the size of the subarray. It keeps breaking each of the subarrays until there ...
Hinko Pih Pih's user avatar
8 votes
1 answer
3k views

Worst-case input for median-of-medians with groups of size 3

Typically, median of medians algorithm is written with groups of size $5$ or $7$ to ensure worst-case linear performance. The argument against groups of size $k=3$ is typically that we get a ...
ryan's user avatar
  • 4,391
8 votes
2 answers
295 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 ...
user avatar
7 votes
2 answers
3k views

Is the Berkeley tutorial on Fibonacci trees using wrong figures?

I'm confused about the figures in a Berkeley tutorial on Fibonacci trees, which depicts fibtree(2) as and fibtree(3) as I thought fibtree(3) looks like the following (the figure is adapted from ...
JJJohn's user avatar
  • 588
7 votes
2 answers
27k views

How to calculate the mergesort time complexity?

Recently while reading a book (Skienna) I came across the following statement: Mergesort works by dividing nodes in half at each level until the number of nodes becomes 1 hence total number of ...
vivek's user avatar
  • 199
6 votes
2 answers
2k views

How to go from a recurrence relation to a final complexity

I have an algorithm, shown below, that I need to analyze. Because it's recursive in nature I set up a recurrence relation. ...
Chris Bond's user avatar
6 votes
1 answer
318 views

How can the class of tail recursive functions be compared to the classes of PR and R?

How can the class of tail recursive functions (TR) be compared to the classes of primitive recursive functions (PR) and recursive functions (R)? The computation of a PR function always halts. This ...
Peter's user avatar
  • 361
6 votes
1 answer
19k views

Can Breadth-First Search be Implemented Recursively without Data Structures?

I'm in a data structures course, but our current unit discusses recursion and not data structures, and I need to implement breadth-first recursion for the purpose of finding the shortest path through ...
Kiran Ganeshan's user avatar
6 votes
2 answers
317 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. -- ...
aphorisme's user avatar
  • 163
6 votes
1 answer
11k views

Space complexity analysis of binary recursive sum algorithm

I was reading page 147 of Goodrich and Tamassia, Data Structures and Algorithms in Java, 3rd Ed. (Google books). It gives example of linear sum algorithm which uses linear recursion to calculate sum ...
Mahesha999's user avatar
  • 1,745
6 votes
1 answer
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 ...
Spacey's user avatar
  • 161
6 votes
1 answer
449 views

Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems

I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences. The first problem I solved was longest palindromic substring ...
Arat254's user avatar
  • 227
6 votes
1 answer
949 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 [1] [2] seems to skip over whatever details that would make me comfortable ...
lsund's user avatar
  • 61
6 votes
2 answers
1k views

What is the formal justification for the correctness of the second formulation of rod cutting DP solution

CLRS on section 15.1 3rd edition has a good discussion of the rod cutting problem. I will add a description at the end of the question for reference. Define $r_j$ to be the optimal way to cut a rod ...
Charlie Parker's user avatar
6 votes
1 answer
714 views

Inductive vs. recursive definition

When should I call a definition recursive and when should I call it inductive? I have read Carl Mummert's nice answer on MSE. So if I understand correctly we refer to definitions of objects like ...
Kaveh's user avatar
  • 21.9k
5 votes
4 answers
8k views

What's the Big O runtime of a DFS word search through a matrix?

The problem is to try and find a word in a 2D matrix of characters: Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent ...
mcfroob's user avatar
  • 169
5 votes
1 answer
385 views

What does Tarski's Fixed-Point theorem give us that that Y-Combinator does't

I'm taking a graduate course on the theory of functional programming, based on Paul Taylor's "Practical Foundations of Mathematics." I understand the statement of Tarski's theorem about how for any $\...
jmite's user avatar
  • 29.5k
5 votes
2 answers
2k views

Why does the recurrence equation for QuickSort consider all the elements in the array?

I have been taught that QuickSort has the following recurrence equation in the best case: $T(n) = \begin{cases} c & \text{if } n=1 \\ 2\ T(\frac{n}{2}) + c \...
logo_writer's user avatar
5 votes
1 answer
1k views

Algorithm to find maximum number of floors you can check with N eggs and D maximum drops

Question: You are given access to a multistory building. You have N eggs and are allowed D maximum drops from their window. Rules: If a egg is dropped from window of floor F and it breaks, it will ...
Smart Home's user avatar
5 votes
1 answer
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$ ...
user3280193's user avatar
5 votes
1 answer
2k views

Since we need space for recursive calls, is the space complexity of the recursive factorial is n?

As Wikipedia says, quickSort needs O(log n) extra space when the following conditions are met: In-place partitioning is used. This unstable partition requires O(1) space. After partitioning, the ...
Maksim Dmitriev's user avatar
5 votes
1 answer
175 views

Unrolling multi-variable mu (μ) expressions in type theory

Unrolling an iso-recursive μ-type expression such as, say, one isomorphic to natural numbers: μα.1+α using ...
user2023370's user avatar
5 votes
2 answers
12k views

A Recursive Formula For Generalized Josephus problem

The Josephus Problem asks where to start taking out every kth person in the circle consisted of n people, such that you are the last "survivor". The following recursive formula is given: $$\begin{...
Parisa's user avatar
  • 121
5 votes
1 answer
107 views

How to show all possible implied parenthesis?

Can I use recursion to find out the possible parenthesis we can add to this expression: 2*3-4*5 ? (2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = ...
noman pouigt's user avatar
5 votes
1 answer
251 views

Proof by induction over rules for mutually recursive relations

Consider the (big-step) semantics of a language ($a, e$ terms, $v$ values), defined by two mutually recursive relations, $\downarrow$ and $\Downarrow$, given by a set of rule-schemata (simplified): $\...
choeger's user avatar
  • 610
5 votes
3 answers
3k views

Can any recursion implementation be written as tail-recursion?

Can any method that uses recursion be written as tail-recursion?
Glide's user avatar
  • 153
5 votes
2 answers
5k views

single algorithm to work on both directed and undirected graph to detect cycles?

I have been trying to implement an algorithm to detect cycles (probably how many of them) in a directed and undirected graph. That is the code should apply for both ...
user1988876's user avatar
5 votes
0 answers
54 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,...
Greg Peckory's user avatar

1
2 3 4 5
12