# Questions tagged [recursion]

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

367 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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$ ...
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 ...
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 ...
179 views

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 ...
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....
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 ...
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$ ...
502 views

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 ...
259 views

### Reccurence of recursive function with unequal sizes of subproblems [duplicate]

Given pseudocode: ...
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))$ ...
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: ...
6k views

### Finding the time complexity of fibonacci sequence [closed]

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

### Runtime of a recursive algorithm

I have a simple recursive solution as below: ...
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? ...
156 views

### Time-complexity of recursive defined code [duplicate]

How would I set up a recursive formula for time-complexity for this code: ...
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 ...
91 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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}...