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

Recursive relationships for ternary strings

If one were to have a ternary string with no repetition of consecutive $0$'s or $1$'s how would you define the recursive relation? The first way I tried to solve was to assume $2$ was the last digit where we could have $a_{n-1}$ possible…
user215721
  • 11
1
vote
1 answer

Counting Regions when cutting a circle (recursion)

Let m≥1 and n≥1 be integers. Consider m horizontal lines and n non-horizontal lines such that no two of the non-horizontal lines are parallel, no three of the m+n lines intersect in one single point. These lines divide the plane into regions (some…
user2847624
  • 71
1
vote
2 answers

How can I prove that two recursion equations are equivalent?

I have two recursion equations that seem to be equivalent. I need a method to show the equivalence relation between them. The equations calculate number of ones in binary representation of the number. The equations are given below: 1) $$ f(0) =…
3878801resu
  • 111
0
votes
2 answers

If $T(0) = 0$ and $T(n>0) = 2T(n-1)+4^n+1$, what is the explicit formula (via recursion)?

All I know is that you'd have to use substitution to get rid of $T(n-1)$ and summations for the rest, but whenever I work through it I get to $2^{(n+2)}+2^{(n-1)}-2.5$ which is not the correct answer (checked via excel).
Zain Virani
  • 5
0
votes
2 answers

given a total width and a given number of decreasing widths to fit that width, what is the % decrease

Hailing from the programming world here, maths has never been my strongest area. I have a width (TW), and that width must be divided by a given number(N) of smaller widths which decrease incrementally. They should decrease by the same percentage…
Melbourne2991
  • 101
0
votes
1 answer

Why characteristic function is primitive recursive

I'm studying recursive functions and right now I stucked in this: "Natural numbers subset is PR if and only if characteristic function is PR". Why is that? Becouse it has values 0 ant s(0) only? So how about set {1, 2, 5} is it PR? If so, that…
Martynas Riauka
  • 339
  • 1
  • 13
0
votes
4 answers

Given n flips, what is the expected number of times the sequence HT shows up?

Suppose a fair coin is flipped $n$ times - what is the expected number of appearances of the sequence HT? I know it's $\sqrt n$, can anyone provide an explanation why this is true?
John Smith
  • 9
0
votes
1 answer

How to deduce from a recursive variant of the triangular numbers the non-recursive form?

This is probably simple (if not, my apologies beforehand), but I have the following formula: $$f(0) = 2$$ $$f(x) = 6x + 2 + f(x -1) \; \text{ where } x \in \mathbb{N}_{\gt 0}$$ The formula actually represents a quadratic performance in a certain…
Abel
  • 219
0
votes
1 answer

computer recursion same question but omitting defdef

Given the alphabet {a,b}, give a recursive definition for the language whose words don't contain the string aa. My solution is i) b ∈ L1 ii) if w ∈ L1, then so is wba, abw My question is should i include a in rule i)?
user120161
  • 27
0
votes
1 answer

recursive definition of strings

I have been unable to find any examples that resemble this problem and I am having issues with recursion. Here is the problem: Give a recursive definition for the set of strings of letters a, b, c, d, e, f, g, h (and only these 8 letters) that…
user120161
  • 27
0
votes
2 answers

Recursive definition attempt.

I have the following question: $\text{b) }$Give a recursive definition for the function $f:\Bbb N\to\Bbb N$ which calculates the following sum for any $x\in\mathbb N$: $$f(x)=20+(20+1)+\ldots+(20+x)$$ For example, $f(2)=20+(20+1)+(20+2)$. $f(x) =…
user120282
  • 21
0
votes
2 answers

proof by induction question

I decided to try proof by induction without any help = ) so if someone could check it out, pretty sure it's unfinished or, well i'm not sure. Also, if possible, could you take a logical guess for how many marks i'd get /10 for what I've done atm…
user118964
  • 11
0
votes
2 answers

Recursion function question again

http://vvcap.net/db/3RxO1KX2d4LxgD714Tyh.htp mult(x,y)= mult(x-1,y)+4 mult(0,4)=0 mult(1,4)=mult(0,4)+4 mult(2,4)=mult(1,4)+4 mult(3,4)=mult(2,4)+4 I'm not sure whether this is correct, but i think it does calculate the four time tables ? since it's…
user118918
  • 3
0
votes
1 answer

how I prove a valid recursion?

Determine whether is this a valid recursive definition of a function f from the set of nonnegative integers to the set of integers. If f is well defined (valid recursion), find a formula for f(n) when n is a nonnegative integer and prove your…
Rich Sanchez
  • 69
0
votes
1 answer

Solve a simple exponential recursive equation?

I want to fill a range between two values, not linearly but exponentially. For this I use a starting value L take exponent R, and repeat for N number of steps. L = 1e-7 R = 0.9997 # needs solving N = 1000 for _ in range(N): L = L ** R >>>…
Anonymous
  • 233
  • 1
  • 10
1 2 3
…
12 13