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

Symmetric Set recursive functions

What do you call a function that takes an ordered set S of reals to a real and has the property that f(S) = f({f({S-{x}),x}) for all x in S? Ex summing a set of numbers. You can take out one number sum the rest then sum the partial sum with the…
Ken
  • 347
0
votes
0 answers

Question about explicit formula of recursive equation

Let's operator $ \overset {k}{\underset{i =n}{ \lower 3pt { \LARGE\Xi}}}a_i $ means to add all possible products $a_i$ in such way, that sum of their indexs equal to n and the amount of elements of that produkt is equal to k. eqamples $ \overset…
Intruder
  • 1
0
votes
0 answers

Recursion on predicate language

Is it possible to write any expression in the language of first-order predicates that would essentially be a recursion, that is, something similar to iteration in a loop?
Mult1fruct
  • 1
0
votes
0 answers

Proving the Time Complexity of T(n) = T(n-1) + T(n-2) + T(n-4) + c is O(3^n)

I am currently analyzing the time complexity of a recursive function, T(n), defined as T(n) = T(n-1) + T(n-2) + T(n-4) + c, where c is a constant. To prove that the time complexity of T(n) is O(3^n), I am following an example that demonstrates the…
misha
  • 1
0
votes
1 answer

How to solve the equation T(n) = 3T(n/3) + 3n

Task: Solve the recurrence equation: $$T(n) = 3T\left( \frac{n}{3} \right) + 3n$$ Assume $T(0) = T(1) = O(1)$. My approach is: $$T\left( \frac{n}{3} \right) = 3T\left( \frac{n}{9} \right) + \left( \frac{3n}{3} \right) = 3T\left( \frac{n}{9} \right)…
user1185546
0
votes
0 answers

Find recursion for number of strings length of n above {$A,B,C$} without AA and BB

Okay, I tried something, got close, but no idea why my answer is wrong. I pick C >> $n-1$ options. I Pick A (Here is problem): A = n-1 options -(subtracting) (AB = n-2 options - ABB = n-3 options)) Which gets me: $a_n = 2a_{n-1} - a_{n-2} +…
user1038824
0
votes
0 answers

Decomposing a number using array of integers

I've got a problem I'm working on and I can't seem to make progress, so I thought it'd be a good idea to ask around if anyone has an input for me. I will try to explain it: Q: Numbers can be written as a sum of other numbers. Say, 7, can be written…
WildDracula
  • 1
0
votes
1 answer

Proper Definition for Recursive Series

I came across this definition of recursive series in a textbook. It goes as follows: $$a_0 = 0$$ For all $n \in N$, $$a_{n+1} = 2a_{n}+n$$ I am not sure if this is just me being silly, but I somehow find the $a_{1}$ term to be awkward to fit into…
Sigsevduh
  • 1
0
votes
1 answer

sum of recursion relation

how should I write the recursion relation using the $\Sigma$ ? we have $\begin{equation*} T(n) = \begin{cases} 1 &n=0\\ T(n-1)+n &n>0 \end{cases} \end{equation*}$ so if we suppose we reached the end, the recursion relation is :…
MR.-c
  • 119
0
votes
1 answer

How to solve reccursive function with 2 variables

So I have a problem where I need to sum over a recursive function. The problem is that it is a 2 variables function and I can’t find any information on how to solve it. I know how to do it with 1 variable, but not with 2. The…
Omri Bar Oz
  • 1
0
votes
2 answers

How to block this recursive equation

Just trying to solve this recursive equation. I tried to use an iteration method and I'm struggling to understand how to determine when the iteration is over (first iteration: $n^{0.5}$, second $n^{0.25}$, third $n^{0.125}$). $$T(n) = T(\sqrt{n}) +…
yuval
  • 77
  • 7
0
votes
2 answers

Coin Recurrence Game

Hi I'm struggling with the following homework problem: Let's play a game. We start with $n$ coins side by side in a row which all happen to be heads. We apply the following operation to the row until we can't any more. As we traverse through the row…
menalaus
  • 1
0
votes
1 answer

Give a recursive definition of the set: $C:= \{ \frac{1}{3^2}, \frac{1}{6^2}, \frac {1}{9^2}, \frac{1}{12^2}, \frac{1}{15^2} \ldots \}$

Question: Give a recursive definition of the set: $$C:= \left\{ \frac{1}{3^2}, \frac{1}{6^2}, \frac {1}{9^2}, \frac{1}{12^2}, \frac{1}{15^2}, \ldots \right\}$$ So I see this as the set $\left\{ \frac{1}{(3k)^2}\right\}$ for integers $k$ with $k…
IntegrateThis
  • 3,778
0
votes
1 answer

How to convert recursive to closed form

For example if $f(x+1)=af(x)+b$ is there a way to find the closed form? Like what is $f(x+1)=\frac67f(x)+\frac67$ is closed form?
qwerty uiop
  • 23
0
votes
1 answer

Is n over itself, over itself ... recursively equal to one, or square-root of n?

Suppose that $x = \frac{n}{x} $ where n a constant real number and we wish to solve for x. Solving analytically, $x^2 = n \rightarrow x = \sqrt{n}$. But, suppose we plugged in the value of x recursively so that $x =…
Alex F.
  • 63
1 2 3
…
12 13