Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [recursion]

Recursion is the process of repeating items in a self-similar way. A recursive definition (or inductive definition) in mathematical logic and computer science is used to define an object in terms of itself. A recursive definition of a function defines values of a function for some inputs in terms of the values of the same function on other inputs. Please use the tag 'computability' instead for questions about "recursive functions" in computability theory

Recursion is the process of repeating items in a self-similar way. The most common application of recursion is in mathematics and computer science, in which it refers to a method of defining functions in which the function being defined is applied within its own definition.

Basically, a class of objects exhibiting recursive behaviour can be characterised by two features:

  • There must be a base criterion for which the function should not call itself.

  • Every other iteration of the function should move it closer to the base condition.

2829 questions
2
votes
0 answers

Recursion for strings: Is this correct

My question is pretty straightforward: Give a recursive definition for the set of all strings of a’s and b’s, where all the strings are of even length. I have attempted to solve the above question and I was wondering if you could tell me if my…
bcsoccer5
  • 21
2
votes
2 answers

Recursive sequence with square roots

Let $a_0 = -2, b_0 = 1,$ and for $n \geq 0,$ let $$a_{n+1} = a_n + b_n + \sqrt{a_n^2 + b_n^2}$$ $$b_{n+1} = a_n + b_n - \sqrt{a_n^2 + b_n^2}.$$ Find $\frac{1}{a_{2012}} + \frac{1}{b_{2012}}.$ Originally I tried looking for a pattern for smaller…
questionasker
  • 1,148
2
votes
2 answers

Solving recursive function with floor

The recursive function is this: $$ T(n) = \begin{cases} 2 & \text{ for }n=1;\\ T \left( \lfloor \frac{n}{2} \rfloor \right) + 7 &,\text{ otherwise} \end{cases} $$ Based on the definition of the function, the right side becomes: $T(n) = T( \lfloor…
Toni Ivanov
  • 63
2
votes
1 answer

Tower of Hanoi (for C, Python, or Java)

I am not fully understanding the Towers of Hanoi. The recursion is very elegant and the answer has eluded me for a very long time. I am currently learning python, so lets use python. def TowerOfHanoi(n,from_rod, to_rod, aux_rod): if n==1: …
Jordan Greenhut
  • 143
2
votes
1 answer

Primitive recursive identification of the digits into a binary expression.

I would like to know which is the form of the primitive recursive function that gives the i-th digit of the binary expression of a given number.
gibarian
  • 145
2
votes
1 answer

How to analyze this recursion?

How can I analyze this recursion for $k>0$? $$T(n)=n+T\left(\frac{n}{2}\right)+T\left(\frac{n}{4}\right)+T\left(\frac{n}{8}\right)+\cdots+T\left(\frac{n}{2^k}\right)$$ I want to prove that $T(n)=\theta(n\log(n))$. Is it true that…
user337036
2
votes
1 answer

Recursion equation and finding odd prime factor

I was randomly browsing on a site which contains questions from various topics of science and mathematics and I found this problem:- Then I tried to solve it but could only proceed till the general solution of the sequence which…
Anish Ray
  • 857
2
votes
1 answer

proof of a recursive relation

I am currently reading a paper where they refer to the following recursive relation: For $i \geq 1$, $a_i = \sum_{j=0}^{i-1} \frac{(-1)^j}{j!}$. Then we get $a_1 = 1, a_2 = 0$ and $a_j = \frac{1}{j-1} \sum_{i=1}^{j-2} a_i$ for $j \geq 2$.…
boukkoun
  • 323
2
votes
0 answers

Induction for recurrence: $t(n) = t(n/2) + \log_2 (n)$

Assume $t(1) = 0$. Assume $n$ is a power of $2$, so $n = 2^m$ or $m = \log_2 n$. I am first asked to solve the recurrence, then asked to prove my answer by induction. I solved the recurrence and got $O((\log_2(n)^2)$, but dont understand the second…
throwawayguy
  • 21
2
votes
1 answer

Recursion Tower of Hanoi

Consider the standard recursive solution to the Towers of Hanoi problem. In the traditional problem, all moves cost the same. Now, suppose the cost of a move is the size of the disk, with $1$ being the cost of the smallest disk, $2$ the second…
Darkflame
  • 21
2
votes
4 answers

A set of certain lists - does it exist?

Define a placeholder to be either an empty list $()$ or a list $(p q)$ of two placeholders $p$ and $q$. Does it exist a set of all placeholders? Of all finite placeholders? My intention with placeholders is to abstract the structure of expressions…
Lehs
  • 13,791
  • 4
  • 25
  • 77
2
votes
1 answer

$T(n) = \sqrt n\,T(\sqrt n) + n\log n$

I tried to solve this recursion equation with master theory, and it's not working in this way. How many arrays exist in each step in the recursion tree? And how can I solve this problem with another way?
user11001
  • 123
1
vote
1 answer

find formula to count of string

I have to find pattern of count of series. Lenght of series is $2n$. It is neccessary to use exaclty double times every number in range $[1...n]$ and all of neighboring numbers are different. Look at example. $a_0 = 0$ $a_1 = 0$ $a_2 = 2$ …
xawey
  • 13
1
vote
1 answer

Recursive sum of squares of prime numbers

Perfect squares always have recursive sum of their digits(e.g. $361\rightarrow 10 \rightarrow 1$) as either $1, 4, 7$ or $9$. But if the perfect square is square of a prime number, except of $3$ . This recursive sum is always $1,4$ or $7$. Its never…
Deepeshkumar
  • 427
1
vote
1 answer

Maths/Programming recursion question

I know this is a programming question but it seems to be more on the mathematical side ( recursion ) I was hoping someone would be able to explain it to me since it will probably be on my exam tomorrow.…
user120282
  • 21
1 2
3
…
12 13