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
1
vote
2answers
80 views

Give a recursive function $r$ on $A$ that reverses a string

I really need help with this task here. Im stuck at it and I really would appreciate your help Here is the task: Give a recursive function $r$ on $A$ that reverses a string. For instance, $r(logikk) =...
4
votes
1answer
1k views

Recursive equation for complexity: T(n) = log(n) * T(log(n)) + n

For analyzing the running time of an algorithm , I'm stuck with this recursive equation : $$ T(n) = \log(n) \cdot T(\log n) + n $$ Obviously this can't be handled with the use of the Master Theorem, ...
13
votes
4answers
43k views

Complexity of recursive Fibonacci algorithm

Using the following recursive Fibonacci algorithm: def fib(n): if n==0: return 0 elif n==1 return 1 return (fib(n-1)+fib(n-2)) If I input ...
2
votes
3answers
17k views

Printing The Longest Path from Root to Leaf in Binary Tree [duplicate]

I am stumped as to how to print the longest path from the root of a binary tree to a leaf, essentially traversing the height of the tree. I've got the following for finding the height of a binary tree:...
3
votes
1answer
1k views

Complexity of a recursive bignum multiplication algorithm

We have started learning about analysis of recursive algorithms and I got the gist of it. However there are some questions, like the one I'm going to post, that confuse me a little. The exercise ...
2
votes
1answer
470 views

Tight asymptotic bound for recursive algorithm

I have this algorithm where: $$ T(n) = \begin{cases} 1 & \text{if}\; n \le 1 \\ T(n/2) + 1 & \text{otherwise} \\ \end{cases} $$ So, evaluating for $T(0), T(1), T(2), T(3), \ldots, T(n)$, ...
1
vote
3answers
246 views

Ordering a list of lists subject to constraints

I have encountered a surprisingly challenging problem arranging a matrix-like (List of Lists) of values subject to the following constraints (or deciding it is not possible): A matrix of m randomly ...
1
vote
1answer
1k views

Recursive definition of sum of two numbers in terms of the successor function

This is a question from the book Data structures using C and C++ by Tenenbaum. Not a homework problem but self-study. Recursive definition of a+b, where a and b ...
6
votes
1answer
568 views

Inductive vs. recursive definition

When should I call a definition recursive and when should I call it inductive? I have read Carl Mummert's nice answer on MSE. So if I understand correctly we refer to definitions of objects like ...
3
votes
3answers
7k views

Iterative and/or tail-recursive implementations of merge sort?

I recently learned how to implement merge-sort, using a standard recursive algorithm. Can the algorithm be implemented in a way that allows for a tail-recursive implementation? Can it be implemented ...
4
votes
4answers
8k views

Can we create recursive functions only by using if-else statements?

I have to show whether a program containing only if-else statements but no loops is able to calculate the following type of functions: $f^n(x)$. The function $f$ is applied $n$ times to $x$, so I ...
0
votes
1answer
502 views

Time complexity of mutually recursive functions

Suppose I have two mutually recursive functions like this: ...
2
votes
1answer
760 views

Partial recursive function and Turing machine

The wikipedia article about primitive recursion states that An equivalent definition states that a partial recursive function is one that can be computed by a Turing machine. My question is how ...
0
votes
1answer
1k views

Register Machine code for Fibonacci Numbers

I am not sure whether this is the right place to ask this question. I would like to write a register machine code which when given an input of n in register 1, returns (also in register 1) the nth ...
0
votes
1answer
2k views

Particularly Tricky Recurrence Relation (Master's Theorem)

Master's theorem is shown below, The recursive function to be solved is shown below, I understand that a refers to the number of recursive calls in this function (...
11
votes
1answer
2k views

Towers of Hanoi but with arbitrary initial and final configuration

Recently, I came across this problem, a variation of towers of hanoi. Problem statement: Consider the folowing variation of the well know problem Towers of Hanoi: We are given $n$ towers ...
1
vote
1answer
111 views

Resolving this recurrence equation [duplicate]

I have this recurrence equation: $T(n) = T(n/4) + T(3n/4) + \mathcal{O}(n)$ $T(1) = 1$ I know that the result is $\mathcal{O}(n \log n)$ but i don't know how to proceed.
0
votes
1answer
737 views

Proving correctness of the algorithm for convex polygon minimum cost triangulation

I have read many solutions for the minimum cost of triangulation problem and intuitively get the idea , however I am struggling to figure out how to prove it formally. I kind of feel that it has to be ...
1
vote
2answers
172 views

Can a recurrence relation be translated to a composite function of itself?

Perhaps this is a question for stackoverflow because its practical nature, but I am not aware of any general method to relate recurrence relations and recursive functions. Having as an example this ...
0
votes
0answers
32 views

The use of master theorem appriopriately [duplicate]

I have a recurrence relation and trying to use master theorem to solve it. The recurrence relation is: $T(n) = 3T(n/5) + n^{0.5}$ Can I use the master theorem in that relation? If so, can I say that ...
3
votes
2answers
857 views

Need help about solving a recurrence relation

I have a recurrence relation which is like the following: $T(n) = 2T(\frac{n}{2}) + \log_{2}n$ I am using recursion tree method to solve this. And at the end, i came up with the following equation: ...
2
votes
2answers
1k views

Tasks in which recursion is either the fastest or only way to produce a result [duplicate]

I've just finished studying recursion at university. One thing that stood out for me however was that in both the lectures and in the practical we completed, all the tasks we were asked to do could be ...
1
vote
1answer
646 views

Why does backtracking work the way it does?

I just recently started learning in a CS context (as opposed to a programming context) about simple recursive functions, along with the combinatorial applications, and techniques such as Backtracking ...
0
votes
1answer
187 views

A Formula For Generalized Josephus problem

There is a formula in wikipedia for the general case of josepus problem Josephus Problem But there is no reference for it, I don't know where it came from and I need too find out... Maybe Donald ...
2
votes
1answer
383 views

Prove $\varphi(x)$ to be primitive recursive

Let $\varphi(x)=2x$ if $x$ is a perfect square, $\varphi(x) = 2x+1$ otherwise. Show $\varphi$ is primitive recursive. In proving $\varphi$ to be a p.r. function I think it could come in handy the ...
2
votes
1answer
320 views

How to prove “The power set of a countable set must be uncountable”?

I'm not sure if this statement is correct, but my friend said so. The problem arose from this T/F question: Let $F=\{f: f$ be a primitive recursive function from $\mathbb{N}$ to $\mathbb{N}\}$, then $...
3
votes
2answers
2k views

Show $x^y$ is a primitive recursive function

As this thread title gives away I need to prove $x^y$ to be a primitive recursive function. So mathematically speaking, I think the following are the recursion equations, well aware that I am ...
3
votes
1answer
220 views

Clarifications on primitive recursive function definition

I am studying primitive recursive functions and there's something that I don't quite understand: let's take the function that computes $x+y$, then, in order to show that $f(x,y)=x+y$ is primitive ...
0
votes
3answers
1k views

Recursive function calculating number of ways to sum $a + 2 b + 3 c = x$

Using python need to code a recursive function with one input and no global integers that calculates the number of options to get $x$ using $a*1+b*2+c*3$. Say $x=3$, there are four options: $\lbrace (...
4
votes
2answers
9k views

A Recursive Formula For Generalized Josephus problem

The Josephus Problem asks where to start taking out every kth person in the circle consisted of n people, such that you are the last "survivor". The following recursive formula is given: $$\begin{...
1
vote
1answer
891 views

Recursion problem involving head, tail and xor

Consider a set of functions: head(l) returns first bit from list l, e.g. ...
4
votes
1answer
921 views

What is the TAK function for?

We covered this in class today. I understand the mechanics of it, but aside from being a nice example of recursion does it serve any purpose? Searching the web reveals lots of pages with the formula ...
2
votes
1answer
1k views

Minimum weight triangulation

I'm just curious about the pseudocode (or real source code, doesn't matter) of the recursive version of this algorithm. In almost every book chapter/paper when describing this topic, they mention that ...
2
votes
2answers
2k views

Need a practical solution for creating pattern database(5-5-5) for 15-Puzzle

I have asked this exact question on StackOverflow. I did not get the answer that I was looking for. Please read this question fully before answering. Thank You. For static pattern database(5-5-5), see ...
11
votes
3answers
801 views

Do “inductively” and “recursively” have very similar meanings?

Do "inductively" and "recursively" mean very similar? For example, if there is an algorithm that determines a n-dim vector by determine its first k+1 components based on its first k components having ...
70
votes
4answers
66k views

What is tail recursion?

I know the general concept of recursion. I came across the concept of tail recursion while studying the quicksort algorithm. In this video of quick sort algorithm from MIT at 18:30 seconds the ...
4
votes
1answer
730 views

How to show that f(x) is primitive recursive?

Let $$f(x)=\begin{cases} x \quad \text{if Goldbach's conjecture is true }\\ 0 \quad \text{otherwise}\end{cases}$$ Show that f(x) is primitive recursive. I know a primitive recursive ...
3
votes
3answers
172 views

Optimize a linear recurrence

$$\begin{align*} T[1] &= 1 \\ T[2] &= 2 \\ T[i] &= T[i-1] + T[i-3] + T[i-4] & \text{for \(i \gt 2\)} \\ \end{align*}$$ I have to calculate $T[N]$, but $N$ is too big ($\approx ...
3
votes
3answers
1k views

How to write a recursive function that with certain time complexity

I'm now doing exam revision, and from some past year exam papers, I noticed some questions that ask to write a recursive method with signature like ...
6
votes
2answers
2k views

How to go from a recurrence relation to a final complexity

I have an algorithm, shown below, that I need to analyze. Because it's recursive in nature I set up a recurrence relation. ...
1
vote
1answer
395 views

Recursion for runtime of divide and conquer algorithms

A divide and conquer algorithm's work at a specific level can be simplified into the equation: $\qquad \displaystyle O\left(n^d\right) \cdot \left(\frac{a}{b^d}\right)^k$ where $n$ is the size of ...
33
votes
6answers
65k views

What is most efficient for GCD?

I know that Euclid’s algorithm is the best algorithm for getting the GCD (great common divisor) of a list of positive integers. But in practice you can code this algorithm in various ways. (In my case,...
26
votes
5answers
45k views

When to use recursion?

When are some (relatively) basic (think first year college level CS student) instances when one would use recursion instead of just a loop?
14
votes
6answers
3k views

Examples of sophisticated recursive algorithms

I was explaining the famous deterministic linear-time selection algorithm (median of medians algorithm) to a friend. The recursion in this algorithm (while being very simple) is quite sophisticated. ...
10
votes
3answers
4k views

Algorithm to test whether a binary tree is a search tree and count complete branches

I need to create a recursive algorithm to see if a binary tree is a binary search tree as well as count how many complete branches are there (a parent node with both left and right children nodes) ...
22
votes
2answers
3k views

Recursive definitions over an inductive type with nested components

Consider an inductive type which has some recursive occurrences in a nested, but strictly positive location. For example, trees with finite branching with nodes using a generic list data structure to ...

1
6 7 8 9
10