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
3 answers

Fibonacci Sequence help...again

I'm back again stuck on another problem: Solve the recurrence relation: (1) S(1)=1 (2) S(n) =nS(n−1) + n! for n≥2 Here's what I have done so far: Expand: S(n) = nS(n-1) + n! S(n-1) = nS(n-2)+n! S(n) = n [nS(n-2) + n!] + n! => n^2[S(n-2) +…
Sweetcharge
  • 33
0
votes
1 answer

How to simplify recursive expression from a summation?

I have an expression that is similar to this: $$L_0 + (L_0 + L_1) + (L_0 + L_1 + L_2) + (L_0 + L_1 + L_2 + L_3) + .... + (L_0 + L_1 + ... + L_n)$$ How would I be able to simplify this recursive expression?
Naz
  • 3
0
votes
0 answers

How to solve a nonlinear recursion relation?

Given the following recursion relation \begin{equation} E^{(n)}=(E^{(n-1)}-\alpha_1)\,e^{-\alpha_2\,(\alpha_3E^{(n-1)}+b)} \end{equation} where $\alpha_i$'s and $b$ are some constants. I am trying to find $E^{(n)}$ as a function of $E^{(1)}$, but I…
Hawi
  • 1
0
votes
1 answer

given an integer i and a range r of real numbers, i divides ranges exactly in half sequentially, where does i split the next r? (without recursion)

Say I have a range r from a - b, $a\in \mathbb{R}$ and $b\in \mathbb{R} $. Then, I have an integer i. Now, if I were to break the range in half, decrease i, then continue breaking the remaining ranges in half from left to right, decreasing i until i…
SimLeek
  • 3
0
votes
2 answers

Recursion If $a_0=1$， $a_1=3$, $a_2=9$ and $a_{n+3}=a_{n+2}+4a_{n+1}+5a_n$, show $a_n\le 3^n$

If $a_0=1$， $a_1=3$, $a_2=9$ and $a_{n+3}=a_{n+2}+4a_{n+1}+5a_n$, show $a_n\le 3^n$. I don't know how to type it in right format. $n+3$ and such things in the parentheses are small and in the lower right corner. I think this question relates to…
Nie
  • 1
0
votes
2 answers

solve recursion $T(n) = T(\alpha n)+T(\beta n)+\gamma n$

I need solve this recursion: $$T(n) = T(\alpha n)+T(\beta n)+\gamma n$$ I know that for $\alpha +\beta< 1$ solution is $O(n)$ How is for $\alpha + \beta = 1$ and $\alpha + \beta > 1$?
Edison91
  • 1
0
votes
1 answer

Amount of times method is called in recursion

This is kind of a basic question, but its busting my head and I cant seem to grasp it. I know that when a recursive function (e.g: rec(int n)) is called recursively twice: rec(int n): if n > 1: rec(n-1) rec(n-1) The amount of…
wimdetr
  • 103
0
votes
0 answers

The graph of Ackermman function is primitive recursive

For a relation $ R ⊆ ℕ^n $, define the characteristic function $ χ :ℕ^n → ℕ $ such that $ χ(x_1, x_2,..., x_n)=1 $, if $ (x_1,...,x_n) ∈R, χ(x_1,...,x_n)=0 $ otherwise. Say a relation is premitive recursive if its characteristic function is…
user280486
0
votes
1 answer

Recursive Definition

Consider the following informal definition for a function calc(x,y) = (0*y) + (1*y) + … + (x*y) For example, we have that calc(2,5) = (0*5) + (1*5) + (2*5) Give a recursive definition for the function calc. Give a trace to show each step…
M-R
  • 219
0
votes
2 answers

How do you formulate an equation that require its own result to replace one of its unknown?

Is the concept of recursion used in Mathematics as it is in computer science? How would you express it in a formula?
Arthur Mamou-Mani
  • 475
0
votes
2 answers

Solving a recursion relation

I have the recursion relation $y_{k}=k(2j-k+1)y_{k-1}$ and I would like to solve it to obtain $y_{k}=\frac{k!(2j)!}{(2j-k)!}$. Can you provide some hints on how I might proceed? P.S.: $j$ is a constant.
nightmarish
  • 617
0
votes
1 answer

Recursion equation - problem with one same root

i have problem with Recursion equation. It look like this: $x(k+2) + 2x(k+1) + x(k) = 0 $ , $x(0) = 3$, $x(1) = 6$ then i' m gettin: $x^2 + 2x + 1 = 0$ zero value are: $\Delta = 0$ , $x_{0} = -1$ $x(k) = C_{1}x_{1}^{k} + C_{2}x_{2}^{k}$ for $x(0) =…
JohneQue
  • 35
0
votes
1 answer

Recursive to explicit formula from power function

I have a recursive formula of a method $f\left(a,b\right)$: $f\left(a,b\right) = \begin{cases} f\left(a,\lfloor \frac{b}{2} \rfloor\right) \cdot f\left(a,b-\lfloor \frac{b}{2} \rfloor\right) & \text{if $b > 1$} \\ a & \text{if $b = 1$} \\ 0 &…
Frithjof
  • 111
0
votes
1 answer

Recursive definition of natural numbers

I'm doing the exercises in Algorithms and Data Structures in Java, Second Edition, by Adam Drozdek. One question is: The set of natural numbers $\mathbb{N}$ defined at the beginning of this chapter includes the numbers…
josh
  • 35
0
votes
0 answers

De-recursifyng a recursive sequence

I'm working on a recursive function for my IB Maths exploration, of the form $f(x)=f((x+a)^{-b})$ I've worked out a general formula for the n-th term of the sequence when $b = 1$, but whenever I'm trying to apply my knowledge to $b = 2$ or higher I…
WizardOfMenlo
  • 155
1 2 3
…
12 13