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
2,941 questions
0
votes
0
answers
39
views
Variants of Pascal's Triangle [closed]
Suppose we construct a triangle of numbers. At each stage of construction, we take the cone above the current slot and add up everything in that cone to get the new entry. For example $76=20+26+4+8+8+...
- 11.9k
4
votes
2
answers
543
views
Trying to figure out a function in set theory formally
I was playing around with a function in set theory, and I came out with this function :
$S(\emptyset) = \lbrace\emptyset \rbrace $
$S(S(\emptyset)) = \lbrace \emptyset, \lbrace\emptyset \rbrace \...
- 483
7
votes
1
answer
148
views
Is the fixed point provided by Kleene's recursion theorem computable?
So Kleene's Recursion theorem states:
Given a computable total function $f:\mathbb{N}\to \mathbb{N}$, there is some $e\in \mathbb{N}$ such that $\varphi_e=\varphi_{f(e)}$.
where $\varphi_n$ denotes ...
- 387
-1
votes
0
answers
93
views
The Existence of an Optimal Chess Move Function
Chess is a finite, deterministic, two-player zero-sum game with perfect information. By standard game-theoretic reasoning (e.g., backward induction), such a game admits a well-defined minimax value ...
- 21
1
vote
1
answer
102
views
Consecutive Heads
I recently encountered the classic "Consecutive Heads" problem, which asks for the expected number of coin tosses required to obtain $N$ consecutive heads. I am aware of the standard ...
0
votes
1
answer
73
views
case definition of recursive functions
Let $f_1,..,f_n: \mathbb{N} \to \mathbb{N}$ recursive functions and let $\langle R_i : i=1,..,n\rangle$ be a recursive partition of $\mathbb{N}$. Now let $g: \mathbb{N} \to \mathbb{N}$ be defined as:
$...
- 21
3
votes
2
answers
152
views
Is the predecessor condition needed for the recursive definition of a function on integers?
In an old article, a method to recursively define functions on the integer set is presented in the following way:
Let $\rightarrow x$ be the successor function, and let $\leftarrow x$ be the integer ...
- 33
2
votes
1
answer
57
views
First-order formalization of primitive recursive functions
I’m interested in first-order formalisation of primitive recursive functions and its relation to classic arithmetical theories like Peano arithmetic.
Consider a many-sorted first-order theory in the ...
- 61
4
votes
3
answers
1k
views
The rigor of the definition of higher derivative
Here is the definition of $n$-th derivative of a real valued function $f$ defined on an interval:
Let $I \subseteq \mathbb{R}$ be an open interval, let $c \in I$ and let $f: I \to \mathbb{R}$ be a ...
- 55
2
votes
1
answer
118
views
Simpler expression sought for this recursive structure
Will splitting a factorial into odd and even parts give a recursive structure?
I am a student of Mathematics and I am trying to understand factorials. While trying to understand factorials in a bit ...
- 231
1
vote
1
answer
56
views
Burnikel-Ziegler division for base $10^k$
I'm implementing the fast recursive division algorithm by Burnikel and Ziegler. After reading the paper, I have a question about the algorithm on page $14$.
How can I translate steps $1-4$ to a base $...
- 41
1
vote
0
answers
31
views
Total Ordering of a Hierarchy of Collapsing Functions
I was playing around the other day with some representations of the weak Goodstein sequence using polynomials and came across an entire hierarchy of functions which behave similarly to the fast ...
- 77.2k
0
votes
0
answers
31
views
Max–min assignment on a DAG when nodes have candidate values with compatibility constraints
I have a DAG where every node has a (usually small) set of candidate integers. A candidate a is compatible with b if (a | b) or (b | a). For every root I want to choose one candidate per node to ...
- 81
10
votes
5
answers
1k
views
Why Does Tao Use Inductive Language When Giving Recursive Definitions?
I’ve read similar questions, but the answers I found were either contradictory or too advanced for my current level. I’m a computer engineering student, and I’m trying to understand a point in Terence ...
- 111
5
votes
1
answer
167
views
Theorem 3.4 of Soare
I am reading Robert I. Soare's "Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets" for a directed reading course. I am having trouble ...
