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
5answers
587 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
844 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 ...
5
votes
1answer
179 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): $\...
-1
votes
1answer
510 views

Proving correctness of a recursive algorithm using induction

For the program mean(A,n) if n = 1 then return A[n] else return A[n]/n+mean(A,n-1)*(n-1)/n end Show that if the recursive call to ...
-2
votes
1answer
341 views

Using dynamic programming to find the number ofl increasing subsequences [closed]

I got this question today and I'm nowhere near the solution, Given a sequence of real numbers (X1, X2, ..,Xn). write an algorithm as efficient there is, that finds the number of strictly increasing ...
5
votes
1answer
1k 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 ...
0
votes
0answers
159 views

Recursive macros and termination of assembler

A debate has arisen in the course of using an assembler (which does a bit of preprocessing first, but is mainly a static assembler): This particular assembler allows recursive macros to be defined, ...
0
votes
0answers
30 views

Solving $T(n)=2T(n/2) + n \lg n$ , For ex: Counting inversions implemented with full mergesort [duplicate]

How to solve the recurrence equation $T(n)=2T(n/2) + n \lg n$ For ex: I implemented "Counting inversions" with a full mergesort instead of just using merge part, So the outer complexity will be $n \...
2
votes
1answer
116 views

Undecidable definition of pure function?

I am trying to come up with a formal definition for functional purity in a simple programming language (think JavaScript). What I've got so far is this: DEFINITION: A statement is impure if ...
0
votes
0answers
162 views

What is the complexity of this recursive merge of two ordered Python lists?

This is not an assignment, but it is related to my Data Structures class. I just wrote this Python code to merge two ordered python lists. I do know that I could do something like this: list1 + list2....
2
votes
1answer
497 views

Time complexity of linear program? [closed]

I have built a heuristic algorithm for approximately solving an NP complete graph problem by recursive linear relaxations. In each recursion, the algorithm returns a reduced graph, with number of ...
1
vote
1answer
59 views

Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)?

This problem is from Algorithms, problem 2 The Problem Given two sorted list of numbers $X$[1..$n$] and $Y$[1..n]. we need to come up with a O($log n$) time algorithm to find the median of the 2$n$ ...
2
votes
1answer
502 views

How to state a recurrence that expresses the worst case for good pivots?

The Problem Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and $...
5
votes
3answers
1k views

Can any recursion implementation be written as tail-recursion?

Can any method that uses recursion be written as tail-recursion?
1
vote
0answers
2k views

Minimum-Maximum recursive algorithm with a non-even partition, complexity [closed]

So I have been trying to find the recurrence relation of the following algorithm in order to compute its complexity. The following algorithm describes how to find the minimum-maximum element in an ...
0
votes
1answer
102 views

Algorithm to compute a recursive function on a given set [closed]

I am working on a property of a given set of natural numbers and it seems difficult to compute. There is a function 'fun' which takes two inputs, one is the cardinal value and another is the set. If ...
0
votes
1answer
116 views

Recursive algorithm to compute a sum of product like function

I am working on a recursive formula associated with discrete mathematics which seems very difficult to compute. The formula is as follows $F_{i,j}(m)=\sum_{t=j}^{m}\left [ x_{ij}.\sum_{k=1}^{m}\sum_{...
1
vote
0answers
695 views

Finding the $k$th smallest element in union of two sorted arrays

I know that this problem is solvable in linear time with a merge but I want to get a sub-linear algorithm. What I came up is that, if a[k] < b[k] then the $k$th ...
1
vote
2answers
259 views
-2
votes
1answer
675 views

Algorithm to decide the Kleene Star of a Language A

Assume $f$ decides a language $A$ in $O(g(n))$ time, where $n$ is the length of the input string. How to write a recursive algorithm to decide $A^*$ (recursive)? Moreover, can an $O(n^2g(n))$ ...
1
vote
1answer
47 views

Something wrong with this definition of factorial with structural recursion? [closed]

In The Algebra of Programming page 5, the authors defined structural recursion foldn (c, h) over natural numbers: ...
2
votes
1answer
6k views

Finding the time complexity of fibonacci sequence [closed]

I tried it as follows and would like to know if it is correct.
0
votes
1answer
664 views

Runtime of a recursive algorithm

I have a simple recursive solution as below: ...
0
votes
1answer
42 views

What is the name of this size method calculating the size of a node?

My confusion is that if the recursive call calls the left nodes, and then adds with the right nodes, how are the nodes that are to to right of the left nodes and vice versa being called? ...
0
votes
1answer
156 views

Time-complexity of recursive defined code [duplicate]

How would I set up a recursive formula for time-complexity for this code: ...
1
vote
1answer
376 views

Find one-variable recursive formula for running time of Karatsuba multiplication

I'm currently trying trouble to set up the recursive expression for the Karatsuba multiplication of two integers with $n$ and $m$ bits (both having a different number of bits). Usually, the recursion ...
3
votes
2answers
91 views

If $T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$, what is $T(m^2)$?

$T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$ $T(1)=1$ The value of $T(m^2)$ for m ≥ 1 is? Clearly you cannot apply master theorem because it is not of the form $T(n)=aT(\frac{n}{...
2
votes
1answer
192 views

$T(n) = \sqrt{n}\,T(\sqrt{n}) + n\log n$ [duplicate]

I tried to solve the recurrence $T(n) = \sqrt{n}\,T(\sqrt{n}) + n\log n$ with the master theorem but I can't get it to work. How many arrays exist in each step in the recursion tree? Or can I solve ...
1
vote
0answers
42 views

Runtime of “Look and Say” [duplicate]

I am trying to figure out what the time complexity is for a "Look and Say" sequence generator which receives an integer n and outputs the nth term in the look and say sequence. I'm looking at the ...
0
votes
2answers
255 views

Are there any exponential-time iterative algorithms?

Is it possible to implement an exponential-time algorithm using iteration, as opposed to recursion? I didn't have any particular algorithm in mind, I was just thinking theoretically. The way I was ...
0
votes
1answer
111 views

Solving the recurrence $T(n) = 2^{n/2}T(n/2) + 2^n$ using a recursion tree [duplicate]

I have homework from recursion tree and despite my search for hours I could not find the answer to this problem. I appreciate if you can help. Draw a recursion tree and give a tight asymptotic ...
2
votes
1answer
2k views

Average time to solve maze through backtracking

Given a set A consisting of all possible solvable mazes on an n by n square grid, what is the average running time to solve the mazes in A using a standard backtrack algorithm with no optimizations? ...
3
votes
3answers
87 views

Recursive methods with stacks

I'm doing some practice papers for revision for my finals and I came across this question: "This question is about recursion. A recursive method can always be implemented by an iterative method ...
15
votes
2answers
892 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 ...
0
votes
0answers
32 views

Proof of the base case of Big Theta using induction [duplicate]

Here is a recursive definition for the runtime of some unspecified function. a and c are positive constants. $T(n)=a$, if $n=2$ $T(n)=2T(n/2)+cn$ if $n>2$ Use induction to prove that $T(n)=\...
2
votes
1answer
1k views

Proof of big theta using induction [duplicate]

Here is a recursive definition for the runtime of some unspecified function. $a$ and $c$ are positive constants. $T(n) = a$, if $n = 2$ $T(n) = 2T(n/2) + cn$ if $n > 2$ Use induction to prove ...
-1
votes
1answer
323 views

Recursion problem to see if string fits in given pattern

If you are given a pattern and a string, check recursively if the string fits in the pattern. The given pattern will be like "dooo?g*a". A question mark can be replaced with one character and asterisk ...
-1
votes
1answer
2k views

What are activation records?

What are the open activation records of a recursive algorithm ? Edit: Activation records are the number of times that we call a function that is not finished yet. Correct? So we can find the number ...
7
votes
4answers
3k 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 ...
-3
votes
1answer
300 views

How much money do you need to pay for pilots and their assistants? [closed]

I am new in writing recursive algorithm so I tried this problem from SPOJ but I could not formulate the recursive relation from where I can find the optimal solution. Can anyone help me to see the ...
0
votes
2answers
99 views

Recursion: base case vs. small version

I'm reviewing the definition of recursion and in my notes are two questions about a recursive problem. One question asks about the base case, the other one about the small version of the problem, I ...
1
vote
1answer
128 views

How many ways to find a sum totalling n using only certain Integers?

Using an infinite supply of integers of a set S, how many ways are there to reach a sum of n? Clarification: The Integers are arbitrary, positive, and may not include 1. At first I thought it was ...
2
votes
2answers
89 views

Finding number of numbers <= N, containing atleast one of the digits 2,4,6,8

Given an integer $N$, I want to find the number of numbers $\le N$, that contain at least one of the digits from the set $\{2, 4, 6, 8\}$. How do I go about solving this problem? I was thinking of ...
1
vote
0answers
333 views

Can the Sieve of Eratosthenes be adapted to find twin primes

The Sieve of Eratosthenes is an algorithm generate the prime numbers, $2,3,5,7,11,13,...$ by drawing a list of numbers crossing out multiples of the smallest number in the list. Is there anyway to ...
6
votes
1answer
9k 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 ...
0
votes
2answers
91 views

Recursive equations vs. inference rules

It seems to me that recursive equations can always be presented as inference rules. For the forward direction, an example is addition over Peono numerals (built from $O$ and $S(\_)$) $$ \begin{align}...