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
1
vote
1 answer

Another recursive math question

Given the alphabet {def ghi}, give a recursive definition for the language whose words contain the string defdef. My solution is: i) def ∈ L and ghi ∈ L ii) if u = def and w ∈ L*, then so is uu, wuu, uuw, wwuu, uuww, wuuw My question is that I feel…
user120161
  • 27
1
vote
1 answer

computer theory recursion

I am having a bit of trouble understanding recursion and would like a bit of guidance. Consider the recursively defined language, L1: i) x ∈ L1 and y ∈ L1 ii) if w ∈ L1, then so is wxw ∈ L1 I have to list the strings that are less than 7 characters.…
user120161
  • 27
1
vote
1 answer

Principle of recursion for inductively defined relations

If we consider a relation $R$ and then its symmetric-reflexive-transitive closure --say $R^*$--, is there a recursion principle associated with $R^*$? It seems to me that such unique function is not able to distinguish between the…
Alistair -L.
  • 163
  • 4
1
vote
1 answer

Recursion Master Theorem

I know that the master theorem states that if $n=d^k$: $$ T(n) = CT(n/d) + f(n)\text{ for }k >= 1\text{ and }T(1)= 1 $$ then $$ T(n)=\sum_{j= 0}^k C^j f(n/d^j) $$ Then how do I get $T(n) = k+1$ when solving $T(n) = T(n/2) +1)$ for $n = 2^k$ and…
Kris
  • 23
1
vote
1 answer

Recursion without halting case

Let's say we have an operator ⨁ which is recursively defined as such: a ⊆ ℤ; b ∈ ℤ a ⨁ b = (a ∪ {b}) ⨁ (b + 1) This definition has no "halting case". Intuitively, it adds b to the set a, then adds b+1 to a, and so on. What is ∅ ⨁ 0? Is this even…
Chirmol Studio
  • 71
1
vote
2 answers

How do you set up this recursive system?

Here is the problem: Emma wants to climb a 12-step staircase. She can climb either 1 or 2 steps at a time. In how many ways can she climb the staircase? I first set $F_{n}$ as the number of steps it takes to get to $n$ stairs. To get from the $n-2$…
Laura
  • 25
  • 4
1
vote
2 answers

First Order Recursion: $T(0) = 0$ and $T(n) = 3T(n/2) + n, n \geq 1$

Well I got this problem: $$T(0) = 0$$ $$T(n) = 3T(n/2) + n, n \geq 1$$ I simplified the equation to the following. $$3^iT(n/2^i) + 2n((3/2)^i - 1)$$ From this point I am confused how to solve. Thanks for any help.
Kris
  • 23
1
vote
1 answer

Trouble understanding recursion in lines dividing a plane.

In how many maximum regions does $n$ lines divide a plane into? It has a well-known recursive formula: $a_{n+1}=a_n+n+1$, where $a_n$ is the number of regions that $n$ lines divide a plane into. I am having a bit trouble understanding the logic…
Ellie_Wong
  • 222
  • 8
1
vote
0 answers

Is there a way to write a recursive formula as a sum from 1 to n (or in any other non-recursive way?

What I would like is a formula that tells me the probability of winning a game given what "state" the game is in. I have denoted the "states" of the game as $K_i$ and I have defined a recursive function $\phi(K_i)$ that gives the probabilities of…
Mathematical Dummy
  • 326
  • 1
  • 6
1
vote
0 answers

Simple Recursion Definition

I have the following equation which is what f is equals to, and am told to write the recursive definition for it. I know that the base case is simply: when n = 0, we can say that the function f = 0^2+2(0)+1 = 1 However, for the recursive definition…
FrenchToast
  • 21
1
vote
2 answers

what is the explicit form of this iterativ formular

I am not sure, if there is an explicit form, but if there is, how do I get it? This is the formula: $$c_n=\frac{1-n \cdot c_{n-1}}{\lambda}$$ where $\lambda \in \mathbb{R}$ and $n \in \mathbb{N}$ I already tried some forms for c via trail and error,…
kyra
  • 257
1
vote
1 answer

Recursive String Proof

Have I done this right? I have shown that every element of Σ exists in Σ*, so is it ok to do what I did in step 5? If Σ = {s,i, n, g}, show that singing is in Σ*. Solution: (in 5 steps) 1) Since λ ∊ Σ* and i ∊ Σ, i ∊ Σ*. 2) Since i ∊ Σ*…
Hermes Trismegistus
  • 429
1
vote
0 answers

Method of solving the recursive relation, $T(n)=T(n/3)+T(2n/3)+n$

I've read on an online forum that one of the methods to solving the recursive relation $\;T(n) = T(n/3) + T(2n/3) + n\;$ is to apply the master's theorem. It says that we can first solve $\;T(n/3) + n\;$ and use its answer in $\;T(n)\;$ (…
NewbieToCoding
  • 123
1
vote
3 answers

Calculating loan + interest recursively

I am trying to calculate a loan amount where the total principle depends on the payment amount. Here's a simple example, leaving aside that a) no bank would actually do this, and b) my income is not specified: I have $0 in the bank right now. I want…
spencerrecneps
  • 113
1
vote
2 answers

Inductive proof for recursive formula $a_n=4-a_{n-1}$

I have a recursive formula $a_n=4-a_{n-1}, a_3=7$ and I had to solve this and check the correction of the answer with induction. I started solving this and the solved formula is: $a_n=-2((-1)^{n-3}-1)+7(-1)^{n-3}$. Base case $n=3$ is true Let's…
Nika Chelidze
  • 189
1 2 3
…
12 13