# 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

1,720 questions
2answers
52 views

0answers
38 views

### Recurrence relationship for crawling a directory

I am trying to write a recurrence relationship for problems that can be solved using recurrence. As an example recurrent for finding the 3^4 (which is 3*3*3*3) can be written as: ...
3answers
44 views

0answers
36 views

0answers
24 views

### Non existence of certain hyperarithmetical functions

In what follows, $\phi_n$ is the $n$th partial recursive function, and $\phi_n^g$ is the $n$th partial recursive function with oracle $g$. We say $x\in\mathbb{N}$ is pre-total if the following two ...
2answers
18 views

5answers
108 views

### Can $a(n) = \frac{n}{n+1}$ be written recursively?

Take the sequence $$\frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}, \frac{6}{7}, \dots$$ Algebraically it can be written as $$a(n) = \frac{n}{n + 1}$$ Can you write this as a ...
1answer
37 views

### Deterministic rule sets and unique $\Phi$-proofs

I'm studying generalized inductive definitions and I got the following question; here, I use the "rule" definition of a g.i.d., instead of the monotone operator approach. So let $\Phi$ be a set of ...
0answers
30 views

### Explicit formula for recursive equation

I would like to find the explicit formula for $f(a)$, where the recursive formula is $f(a)=(a^2+r^2)p-q^2-f(r)$, $p=\lfloor 1+\log_2 a \rfloor$, $q = 2^p$, and $r=q-a$. The base case is $f(1) = -1$. ...
5answers
32 views

### Finding a formula for $f(n)$: $f(0)=1, f(1)=2, f(n)=2f(n-2)$ for $n \ge 2$

I had a hard time figuring out a formula for this. Is there a trick that could be used? The formula in the back of the book is $2^{\lfloor \frac{n+1}{2}\rfloor}$ for $n > 0$.
0answers
25 views

### Does the series of the inverse of 10 to the power of the Recaman sequence converge?

I was wondering if the following series converged: $$\sum^\infty_{n=0}\frac{1}{10^{R_n}}$$ Where $R_n$ is the n-th number in the Recaman sequence. My original thoughts were that it would converge if ...
0answers
37 views