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
13
votes
1answer
2k 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 ...
2
votes
1answer
2k views

What is the time complexity of binary sum (recursion) [duplicate]

Currently, I'm reading Data Structures and Algorithms in Java, 6 edition by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser link, particularly a chapter about recursions. There is an ...
1
vote
1answer
946 views

What is a recursion for Huffman encoding?

If I had to write the Huffman encoding as a recursion in terms of the cost $C_{ij}$, given weights/frequencies $W = [w_1,\ldots,w_n]$, how would I do it? (where this is creating a minimum cost tree, $...
3
votes
1answer
914 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-...
0
votes
1answer
542 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: ...
3
votes
0answers
47 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, ...
1
vote
1answer
219 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 ...
0
votes
1answer
438 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 ...
0
votes
1answer
221 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 ...
4
votes
1answer
10k 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 ...
5
votes
1answer
454 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 ...
2
votes
0answers
49 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 ...
1
vote
2answers
36 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 ...
0
votes
0answers
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 ...
2
votes
1answer
88 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 ...
1
vote
2answers
1k 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 ...
1
vote
2answers
320 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 ...
4
votes
1answer
55 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 ...
-1
votes
1answer
119 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+...
2
votes
2answers
175 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 ...
0
votes
0answers
81 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. ...
1
vote
1answer
435 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-...
2
votes
1answer
626 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. ...
3
votes
0answers
46 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 ...
0
votes
0answers
28 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 ...
0
votes
1answer
62 views

Converting a algorithm to a runtime function

I need to find an upper limit for the runtime of $f(n)$. ...
2
votes
1answer
76 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 ...
17
votes
3answers
11k 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 ...
5
votes
2answers
568 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
votes
2answers
11k 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 ...
2
votes
1answer
223 views

Trying to understand this Dynamic Programming solution

The problem is as follows. Minimize the sum of absolute differences between a matching of $n$ values from two sets, $A=\{a_1,a_2,\cdots, a_n\}$ and the set $B=\{b_1, b_2,\cdots, b_m \}$, with $n\leq ...
5
votes
2answers
1k 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 \...
4
votes
2answers
16k 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 ...
1
vote
1answer
201 views
2
votes
4answers
211 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 ...
0
votes
1answer
357 views

Longest double increasing subsequence (LIS variant)

I'll start with the definitions:Let $S = s_1s_2...s_n$ be a sequence of $n$ integers. A double increasing subsequence of $S$ is a sequence $P=p_1p_2...p_k$ (not necessarily continuous) where for each $...
1
vote
1answer
59 views

Revisiting Fixed Point: What does it mean in the world of computer science?

A while ago I asked Fixed point, what does it mean in the world of computer science? While the answers did help me to understand what Fixed point meant, the answers left me in a murky world when ever ...
2
votes
1answer
596 views

How to treat $\epsilon$ and '$' in top-down predictive parsing (predict table)?

How to treat $\epsilon$ and '\$' in top-down parser using predict table? The construction of the predict table Given a product $X \rightarrow w$, row $X$ and column $t$ -Mark $X \rightarrow w$ ...
1
vote
1answer
509 views

Complexity of dynamic card game algorithm

Consider the following dynamic card game with a regular deck of 26 red cards and 26 black cards. A dealer draws the unturned cards one by one, and we can ask him to stop at any time. For every red ...
-1
votes
1answer
368 views

Complexity and Recurrence relation for Lowest Common Ancestor Binary Tree

I have written this solution for finding the Lowest Common Ancestor in a Binary Tree. Now I wanted to find the time complexity of this problem by solving via recurrence relation. Can someone suggest ...
0
votes
1answer
617 views

Print Binary Tree Diameter Path [duplicate]

Diameter of the tree is defined as a long path or route, between any two nodes in a tree. The path may or may not goes through the ROOT. Print the Longest leaf to leaf path in a binary tree and its ...
2
votes
1answer
402 views

primitive recursion in the lambda calculus

I am having trouble finding out what a primitive subset of the lambda calculus would look like. I reference primitive recursion as shown here: "https://en.wikipedia.org/wiki/...
8
votes
1answer
334 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: ...
3
votes
2answers
1k views

Recurrence relations when function call is made inside loop

int fun (int n) { int x=1, k; if (n==1) return x; for (k=1; k<n; ++k) x = x + fun(k) * fun(n – k); return x; } What is the value of fun(5)? I ...
2
votes
0answers
20 views

What would be the time complexity if a recursive function is inside a loop? [duplicate]

I am confused in calculating the time complexity for a recursive function inside a loop. ...
1
vote
2answers
505 views

How many recursive calls does it take to compute binomial probability weights?

I was given an algorithm and I was asked to estimate how often it would be called if I was trying to calculate ${100 \choose 50}0,25^{50}0.75^{50}$, the Binomial distribution of $50$ elements chosen ...
6
votes
1answer
210 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 ...
2
votes
1answer
64 views

Upper bound of algorithm with flooring

Would much appreciate someone explaining how they managed to get to the upper bound of this algorithm. $$T(n) = 2T(\lfloor \sqrt n\rfloor) + ln (n)$$ $$T(1) = 0$$ Solution is given as: $$T(n) = O(logn*...
5
votes
1answer
96 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) = ...
0
votes
0answers
24 views

How to apply recursion in this problem [duplicate]

Problem Statement : You are situated in an N dimensional grid at position (x1,x2,...,xN). The dimensions of the grid are (D1,D2,...DN). In one step, you can walk one step ahead or behind in any one ...