The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
1
vote
2answers
2k views

Big O notation for recursive algorithm [duplicate]

In order to find Big O for a recursive algorithm, it is needed to know the stopping criteria of that algorithm. For the recursive algorithm to find Factorial of a number it is very easy to find the ...
0
votes
0answers
45 views

Is there a proof for the halting problem that does not involve an infinite nest of functions? [duplicate]

I have been doing a fair amount of research about the halting problem. Most solutions I come across have the following pattern: We assume we have a program H that solves the halting problem. We then ...
2
votes
0answers
57 views

number lesser than a given number composed of only binary numbers

Give a decimal number, such as 123. Need to figure out all smaller numbers lesser than 123 made up by ...
0
votes
1answer
556 views

Recursive Algorithm Copying Array vs. Time Complexity

If I am implementing binary search using a recursive algorithm on an array it will be bounded by $O(\log(n))$. However, what will occur if the array is NOT passed by referenced and rather by value. ...
0
votes
0answers
72 views

Time Complexity — Recursion

It's been a long time since I've studied time complexity in school, but I've been tasked with finding the time complexity of an algorithm. Here is the algorithm in a pseudo-pseudocode (yes, two ...
1
vote
0answers
379 views

Help with deterministic selection algorithm

All we know what is Deterministic Selection Algorithm: Line up elements in groups of five (this number $5$ is not important, it could be e.g. $7$ without changing the algorithm much). Call each group ...
2
votes
0answers
67 views

A question on analysis of the time complexity of a recursive branching algorithm

I'm reading papers on algorithms of maximum independent problem and the basic recursive branching rules is as follows: Let $G(V,E)$ be an $n$-node undirected, simple graph without loops, and $\...
1
vote
0answers
322 views

How to “convert” a top-down solution to a bottom-up algorithm? [duplicate]

When I'm working on a algorithm problem, I can usually find a top-down solution that works with recursion. Then for optimization purpose I try to do a bottom-up approach (dynamic programming) to ...
0
votes
1answer
114 views

If set $C$ is recursively enumerable and $B$ is Recursive, and if $B-C$ is recursively enumerable then is $C$ recursive or not?

So this is how i solve it but someone told me its wrong: $B-C = B\cap \overline C $ and since $B\cap \overline C $ is r.e and B is recursive recursive sets are closed under intersection then $\...
0
votes
0answers
28 views

how to solve Recurtion equation [duplicate]

Does someone know how to solve the below? $$T(n)=2T(n-1)-T(n-2)+5n+7$$ $$T(n)=2T(sqrt(n))+(logn/(log(logn))$$ $$T(n)=T(sqrt(n)[5])+log(log[3]n)$$
0
votes
3answers
463 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 ...
7
votes
2answers
144 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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
1answer
347 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 ...
8
votes
2answers
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 ...
-2
votes
1answer
222 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.
-1
votes
1answer
119 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. ...
1
vote
1answer
157 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 ...
2
votes
1answer
541 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. ...
2
votes
2answers
124 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 ...
0
votes
1answer
211 views

Why is recursive programming problematic for branch predictors

Consider for example the following recursive program: ...
0
votes
0answers
84 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 ...
1
vote
1answer
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 ...
14
votes
2answers
516 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. ...
0
votes
0answers
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 ...
1
vote
2answers
310 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 ...
0
votes
0answers
197 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 ...
0
votes
1answer
163 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, ...
1
vote
1answer
105 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 ...
1
vote
0answers
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. ...
1
vote
3answers
2k 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$: ...
1
vote
1answer
38 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 ...
0
votes
0answers
330 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/...
0
votes
0answers
120 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 ...
0
votes
1answer
522 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?
0
votes
0answers
189 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 ...
0
votes
0answers
46 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 ...
0
votes
0answers
16 views

How to solve this recursive relation T(n)= 2T(n/2) + 3T(n/5) +n [duplicate]

I don't think I'm able to solve this using the master's theorem, and solving separately doesn't seem to make sense. How does one go about solving this recursive relation? T(n)= 2T(n/2) + 3T(n/5) +n
0
votes
0answers
267 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 ...
2
votes
2answers
841 views

Why are unbalanced partitions worse than balanced partitions in Quicksort?

I am unable to understand why unbalanced partitions in quicksort is actually worse than balanced partitions. After reading this document it shows that worse case partitions are of the type $(0,(n-1)),...
1
vote
2answers
214 views

Confusion over the complexity of parameter passing in merge sort

I'm working through CLRS on problem 4-2, which says the following: Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an $N$-element array is ...
1
vote
0answers
26 views

Creating a self-affine fractal on L-systems

Hi I would like to create a self-affine fractal on L-Systems. The axiom I have created is FF-GGG-GG-GGG++GGG+GG-GGG+GG+GGG+FF++ffGG+GGG+FF+GGG which creates the image below At each stage I would like ...
4
votes
1answer
1k views

Recursion Davis' Staircase understanding

I'm going through a hackerrank challenge on recursion https://www.hackerrank.com/challenges/ctci-recursive-staircase and I'm having difficulty understanding how the solution below solves the problem. ...
2
votes
1answer
177 views

what are Structural recursion, primitive recursion, recursion combinator and recursion principles?

Recently, I encountered terminologies such as primitive recursion and recursion combinator. One of the sources is here link I googled and read some, but missing the points of them. I know that ...
2
votes
0answers
195 views

Recursive definitions, How it is done?

I read that recursive definitions, refer to the definition of a function in that function body, cannot be done in $\lambda$-calculus, but recursion can be achieved by using $Y$ combinator. As I know, ...
2
votes
2answers
85 views

Find X contiguous segments in a range of integers

I've been struggling with the following problem: how do I find all possible sub-ranges in a range of integers where each segment is at least length 1, and I specify the total number of segments? A ...
1
vote
1answer
179 views

Rod Cutting without using dynamic approach

Question I want to Implement Rod cutting Algorithm without Dynamic Programming Approach. Let me Describe the problem statement. Given a rod of length $n$ inches and a table of prices $p_{i}$ for $...
1
vote
1answer
663 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 ...
2
votes
1answer
850 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: ...