# Questions tagged [recursion]

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

579 questions
Filter by
Sorted by
Tagged with
718 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$....
• 223
1 vote
11k 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. ...
• 260
475 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 ...
73 views

### Time complexity of 1-d clustering recursive algorithm

I have the following code: ...
• 175
538 views

• 219
1k views

### General method behind converting recursive inorder, preorder and postorder traversals of a binary tree to a non-recursive one?

I am reading both recursive and non-recursive using stack methods to implement inorder, preorder and postorder traversal of a binary tree at https://en.wikipedia.org/wiki/Tree_traversal#Depth-...
• 4,825
1k views

### What is the time complexity (upper bound) for this simple recursive function? [duplicate]

So I have function that I have written to return the maximum value between index i and index x of a given array using recursion as follows: ...
• 137
52 views

### Termination of deterministic term rewriting

Consider a simple language: $$t ::= plus ~ t ~ t ~ | ~ gen ~ t ~ | ~ except ~ N ~ t ~ | ~ N$$ with N constructors plus, gen and except, N being the natural numbers, and $G = \{t_n\}$ a finite, ...
• 610
1 vote
323 views

### Why is this problem listed as "Dynamic Programming"

I found a problem in the dynamic programming section of hackerrank but its not clear why dynamic programming should be used to solve it. The problem is as follows: Nikita just came up with a new ...
776 views

### Algorithm to build a "hand" calculation for riichi mahjong game

I would like to discuss an algorithm to build a "hand" calculation for riichi mahjong game. I will simplify terms to focus on the algorithm and not on the game specific terms. Let's imagine that we ...
• 103
736 views

### Solution to the recurrence T(n) = 2T(n − 3) [duplicate]

We were asked the following question in our exam: Solve or bound the recurrence T(n) = 2T(n − 3) for n>3 provided ...
• 101
20k 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 ...
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 ...
• 390
52 views

### Structural induction in non-local program transformation

Assume a functional language and a specialization operation (pulling out sub-expressions): let f x y = (h 23 x) + (g 42 y) becomes ...
• 610
1 vote
39 views

### Any option other recursive search possible to go from one 2d point to another point with fixed set of possible moves?

Problem: Given (a,b) and (c,d), find if you can you reach from (a,b) to (c,d) if we can only have the following moves (a, b) to either (a+b,b) or to (a,a+b). Example (1,4) to (5,9) is possible ...
• 390
9 views

### Need Help solving Recurrence Problem [duplicate]

I have this practice problem that I was given. I am trying to solve a specific recurrence equation T(n) = 4 when n <= 2 T(n) = 3T(n/3) + 5 when n > 2 ...
137 views

### What kinds of problems are modeled by a recursive definition of a set of strings?

Given this definition: The set $\Sigma^*$ of strings over the alphabet $\Sigma$ is defined recursively by: BASIS STEP: $\lambda \in \Sigma^*$ (where $\lambda$ is the empty string) RECURSIVE ...
• 495
1 vote
2k views

### How to connect the math of recurrence relations to daily programming concepts

What exactly are we doing from a CS perspective when we solve a recurrence relation and find a resulting formula for a sequence given a set of initial conditions? I just went through the "linear ...
• 495
1 vote
413 views

### What is the relationship between tail recursion with other recursions?

I'm rather confused by the recursion theory. From the link, the recursion theory was formed by Dedekind, Gödel and some other famous mathematicians. There are the following types of recursion. But ...
66 views

### How to handle an undefined case with µ-recursive functions?

How to construct my proof and generally what should I aim to get when showing a function is $\mu$-recursive? Should I transform it in some of the basic functions using the given operators? For ...
• 309
132 views

### How to show that certain summations are primitive recursive?

If we have a function $g\colon \mathbb{N}^{k+1} \to \mathbb{N}$ which is primitive-recursive. How to show that the function $f\colon \mathbb{N}^{k+1} \to \mathbb{N}$ with f(x_1, \dots, x_k , x_{k+...
• 175
219 views

### Efficient algorithm for getting from 1 to n with 3 specific operations

The question: Given those 3 valid operations over numbers and an integer $n$: add $1$ to the number multiply the number by $2$ multiply the number by $3$ describe an efficient ...
• 722
87 views

### Figure out recursive function for this problem

I'm trying to solve this problem whole day. The result should be dynamic programming algorithm but the first thing I need is to find out recurrent function. There is N students (N is even) in class. ...
• 329
1 vote
802 views

### Side effect and recursion

My algorithm professor said a recursive function should not have side-effects since it's a methodological error because recursion is "pure". Anyway I don't understand why, even because I find side-...
• 113
1k views

### How does recursion works when there are 2 or more consecutive recursive calls?

I was learning about recursion and i came across the following pseudo code for quicksort. ...
50 views

### Axiomatisation in the presence of recursion

I read Klaus Havelund's thesis on the Fork Calculus: http://havelund.com/Publications/thesis.ps He develops the Fork calculus for reasoning about concurrent functional programs, the motivation being ...
• 359
29 views

### T(n)=T(n-2)+T(n-3)+T(n-4)+2 is O(log n)? [duplicate]

how can i prove that T(n)=T(n-2)+T(n-3)+T(n-4)+2 is O(logn)? or T(n)=T(n-1)+T(n-3)+1 the same.. when T(0)=1 T(1)=2 T(2)=3 T(3)=5 T(4)=8 etc`.. it's a Q about AVL-2 tree,the same rules of AVL tree ...
80 views

### Converting a algorithm to a runtime function

I need to find an upper limit for the runtime of $f(n)$. ...
• 143
178 views

### What Exactly is "Improvement" in Seed AI?

From LessWrongWiki, a seed AI [I]mproves itself by recursively rewriting its own source code without human intervention. Some would even say this could bring about an Intelligence Explosion. Many ...
• 323
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 ...
• 1,006
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 ...
• 2,960
15k views

### How is the complexity of recursive algorithms calculated and do they admit better complexity than non-recursive algorithms?

How are asymptotical time complexities calculated for recursive algorithms? Recursive algorithms call themselves and therefore take up more space compared to non-recursive algorithms. But are they ...
• 129
329 views

• 215
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 ...
• 199
1 vote
378 views

### Why Does the Deterministic Selection Algorithm Run in $O(n)$ and not $O(n\log n)$?

Here is pseudocode for the algorithm: ...
403 views

### Problems understanding proof of smn theorem using Church-Turing thesis

I am reading Barry Cooper's Computability Theory and he states the following as the s-m-n theorem: Let $f:\mathbb{N}^2\mapsto\mathbb{N}$ be a (partial) recursive function. Then there exists a ...
686 views