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
0
votes
0 answers

Recursive definition for $S = \left\{{(a,b) \mid a \in \mathbb{Z}^+, b \in\mathbb{Z}^+ \text{ and } a + b \text{ is odd}}\right\}$

Give a recursive definition of each of these sets of ordered pairs of positive integers. [Hint: Plot the points in the set in the plane and look for lines containing points in the set. $S = \left\{{(a,b) \mid a \in Z^+, b \in Z^+ \text{ and } a + b…
papercuts
  • 1,873
0
votes
0 answers

How can I solve the recursion tree T(n)=2T(n/2)+2/log(n)

I would like to get some help I just don't know how to finish the sum : I got: $$T(n)=2^{k}T(\dfrac{n}{2^k}) + \sum_{i=1}^{log_{2}n} \dfrac{2^{i}}{log(\frac{n}{2^{i-1}})}$$ when $k=log_2n$ I get: $$n+\sum_{i=1}^{log_2n} …
Hodiya2929
  • 1
0
votes
4 answers

Finding formulas for the terms in a recursion defined by $s_1 = 11$ and $s_{n+1}=\frac23(s_n+5)$

Say you have a recursion defined by: $$\begin{align}s_1 &= 11 \\[4pt] s_{n+1} &= \frac23 ( s_n + 5 ) \end{align}$$ I am trying to find an equation that allows the user to put in $n$ and get back the difference change: $s_{n+1} - s_{n}$. I already…
Mardymar
  • 115
0
votes
1 answer

Height of recursion tree

If the recursion is of the form $T(n) = T(n/b) + ...$, the height of the recursion tree is $\log_b n$. My question is if the recursion of the form $T(n) = 2T(n-1) + ...$, the same formula still applies?
trickster
  • 39
0
votes
3 answers

Recursion with strings

Let $A$ be a set of strings on the alphabet ${a, b}$ starting with $a$ and ending with $b$ and they don't have occurrences of $ba$ as a substring. For example, $abab ̸∉ A$, $ab ∈ A$, $abb ∈ A$, $aabab ̸∉ A$, $aaab ∈ A$. (i) Provide a recursive…
user565089
  • 69
  • 3
0
votes
1 answer

Decide how many bacteria there are in a testing tube after n days

In the beginning there are about 1000 bacteria in a testing tube and the amount of bacteria increases every two hours with 250 %. Use a recursion ecvation to tell the amount of bacteria after n days? I made a formula for every two hours but i dont…
Varrens
  • 13
0
votes
1 answer

Presume that $α_1$ and $α_2$ are solutions to the quadratic function, prove that $α_1^n$ and $α_2^n$ fulfill the recursive formula

Presume that $α_1$ and $α_2$ are solutions to the quadratic function, prove that $α_1^n$ and $α_2^n$ fulfill the recursive formula Quadratic function: $x^2 = bx + c$ Recursive formula: $ a_{n+2} = ba_{n+1} + ca_n$ I'm honestly very lost on this one
JohnDoe
  • 465
0
votes
2 answers

The following recursive function defines a linear affine difference equation?

I am trying to solve this example: The following recursive function defines a linear affine difference equation $$x(n+1) = 1.4*x(n) + 0.2$$ $$x(0) = -1$$ Find the first three values of the iteration? Which initial value y(0) would cause the…
Le Chifre
  • 1,277
0
votes
2 answers

Using a notation, find a recursive equation

$\ I_n = \int \cos^n \theta d\theta$ Find a recursive equation to express $\ I_n $ in terms of $\ I_n-_2 $. Find $\ I_6 $ and $\ I_7 $ as well.
neverloggedin
  • 171
0
votes
1 answer

Writing first $5$ terms of recurrence relation

How do I write the first $5$ terms for this recurrence relation? $$S_0=2\\ S_n=S_{n-1}^2 +S_{n-2}^2+\ldots+S_0^2$$ Since I can't substitute $S_0$ directly?
Sook Lim
  • 243
0
votes
1 answer

Recursive definition of Wallis product.

Wallis concluded that $$\frac{\pi}{2} = \frac{4}{3}\cdot\frac{16}{15}\cdot\frac{36}{35}\cdot\frac{64}{63}\cdot....$$ How can one define the right hand side recursively? After a few hours all I could muster was this: $$\begin{cases} a_1=3. \\…
Parseval
  • 6,413
0
votes
1 answer

What does this recursive function does in mathematical therms?

Having this recursive function : int F(int n, int m){ if(m == 0 || m == n) return 1; return F(n-1, m-1) + F(n-1, m); } what is the effect of the function? For the example, F(15, 13) returns 105. I'm struggling to find the answer but…
Gabi
  • 125
0
votes
1 answer

Primitive recursive function for checking if words over binary alphabet are equal

Given the alphabet $A = \{a,b\}^*$ and function $\operatorname{equals}(q,w) = \begin{cases} a, & \text{if } q = w \\ \epsilon, & \text{otherwise} \end{cases}$ How to define primitive recursive function to one above? Just the idea, without proofs…
helloFromTheOtherSide
  • 3
0
votes
2 answers

Recursion and finding formula

I have a question to ask regarding this math question that was given to me. I have no idea on how to start on the question. The formula $1+2+3+...+n=$$$\ \frac {n(n+1)}2$$ is true for all intergers n>=1 If n is an integer and n>=2, find a formula…
Kris
  • 1
0
votes
0 answers

How to write matrix cell piece inequality rigorously?

Let $\alpha = 0.05$. Let p-value $n \times n$ matrix B. Set zero all values which are less than $\alpha$. \begin{equation} B_{k}(i,j) = \begin{cases} 0 \text{ if } B_{k}(i,j) \geq \alpha \\ 1 \text{…
Léo Léopold Hertz 준영
  • 439
1 2 3
…
12 13