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
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
87 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
997 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
313 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
118 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
174 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
79 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
417 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
565 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
74 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 ...
15
votes
3answers
10k 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
1answer
484 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
216 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
970 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
15k 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
195 views
2
votes
4answers
205 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
347 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
577 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
469 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
366 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
596 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
376 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
325 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
485 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
206 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
95 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 ...
1
vote
3answers
109 views

Value returned by recursive function

(pseudocode) ...
3
votes
1answer
310 views

Induction proof of alpha-beta search

Is there a functional specification of alpha-beta search that makes it easy to prove by induction that the algorithm works?
0
votes
0answers
12 views

recursion trees and big theta bounds [duplicate]

Draw recursion trees and use them to find big theta bounds on the solutions to the following recurrences. For each, assume that T(1) = 1 and that n is a power of the appropriate integer. ex) T(n) = 8T(...
2
votes
3answers
80 views

Recursive function problem

This might seem very simple but it's been giving me lots of headaches. For example if I run f(12345) the result is 5310135. I understand why it would return 5310, the rest of 135 is what is giving ...
-1
votes
1answer
364 views

Recursive definition of the set of strings over an alphabet [closed]

The problem is the following: Write the recursive definition for the set of all Strings Q over the alphabet {a, b} (i.e. the set of strings consisting of a's and b', for example a, baba, abbbabababba.....
1
vote
0answers
50 views

Why do we not store the min in any of the recursive clusters in a Van Emde Boas tree?

I was reading the chapter of van Emde Boas in CLRS (page 547 section 20.3 3rd edition) and it says: Furthermore, the element stored in min does not appear in any of the recursive $vEB( \sqrt[\...
2
votes
5answers
581 views

Do recursive algorithms generally perform better than their for-loop counterpart?

I'm sure this is not a challenge for you but it remains an open question for me: Is it wise to prefer a recursive algorithm over its for-loop counterpart? E.g. take the evaluation of the natural ...
4
votes
1answer
827 views

Recursive definition of a language given the regular expression

Consider the language: $$ L_1 = \{ x \in \Sigma^* : x \text{ does not contain the substring } 110\} $$ I know that there is a DFA that accepts this language, and furthermore, that the regular ...
0
votes
1answer
127 views

Help needed with lesson on recursion

I'm studying CS online, and I'm reading this lecture on recursion, see "3.2. A Mathematical Example". I understood the beginning and I even made a program that calculates $X$ to the power of $N$ ...
4
votes
0answers
120 views

Why can't a programming language be both fully recursive and polymorphic

In my theory of computation class last Spring my professor said in passing that a programming language cannot be both fully recursive and polymorphic. I didn't think much of it till now? What does it ...
1
vote
3answers
1k views

If recursive Fibonacci is $O(2^N)$ then why do I get 15 calls for N=5?

I learned that recursive Fibonacci is $O(2^N)$. However, when I implement it and print out the recursive calls that were made, I only get 15 calls for N=5. What I am missing? Should it not be 32 or ...