For questions about defining recursive functions, recursive algorithms and solving recursive equations (e.g, with `RSolve`)
32
votes
2answers
9k views
How can I use Mathematica's graph functions to cheat at Boggle?
This question is inspired by a Stack Overflow question that I decided to solve using Mathematica. In addition to Mathematica, I thought I'd use some of the new version's graph-related functionality, ...
30
votes
4answers
1k views
How can I implement dynamic programming for a function with more than one argument?
Dynamic programming is a technique for avoiding the repeated computation of the same values in a recursive program. Each value computed is immediately stored. If the value is needed again, it is ...
20
votes
4answers
546 views
What tools can help in realizing tail recursion?
I had nice discussions with Leonid and Rojo that got me interested in tail recursion. Tail recursion is not always easy to realize with Mathematica, so it would be nice to have some tools to help with ...
12
votes
3answers
299 views
How to clear parts of a memoized function?
I have a function of two variables, e.g.:
f[a_, b_] := f[a, b] = something f[a - 1, b - 1] etc
With the above code I used the concept of memoization to speed up ...
11
votes
2answers
605 views
How can I solve a difference-differential equation?
How do I ask Mathematica to try to solve a recursive relation that defines a sequence of functions? For example, suppose I know that $g_n(x) = g_{n-1}'(x)$ for $n > 0$ and that $g_0(x) = e^{2x}$. ...
9
votes
6answers
1k views
Recursive function with if-statement
I am trying to represent the following function definition in Mathematica:
$$\begin{align*}
f(1)&=1 \\ f(2n)&= \begin{cases}f(n) & \text{if}\space n\equiv0\pmod{2} \\ 2f(n) & ...
9
votes
2answers
164 views
Can RecurrenceTable make use of CompiledFunction?
I'm trying to implement a discrete-time 2D Verlet algorithm for a point-mass subject to a softened gravitational interaction as a test for a more computationally intensive simulation using ...
8
votes
4answers
179 views
Order items by closest to the previous
I have a list of 2D points (a table, imagine the data of a parametric plot shuffled)
I would like to join the points with a line that starts from one of them and always goes to the closest one.
I ...
7
votes
2answers
268 views
How to deduce a generator formula for a polynomial sequence?
Consider a polynomial sequence $\{p_n\}$ generated by some (simple) rule:
$$
\begin{array}{l}
p_1(x)=x \\
p_2(x)=2 x-x^2 \\
p_3(x)= x^3-3 x^2+3 x \\
p_4(x)=-x^4+4 x^3-6 x^2+4 x \\
p_5(x)= x^5-5 ...
7
votes
1answer
195 views
Setting $RecursionLimit across all parallel kernels
I'm trying to optimize an elliptic curve factoring method by running it in parallel. There is a recursive step which required me to set the recursion limit higher than 256, however when I try and run ...
6
votes
5answers
214 views
How to nest my own “times” function to get powers
I have a "times" function. I'd like to create a power function using it. It should look like this for an 6th power:
...
6
votes
1answer
265 views
Compiling a recursive formula
My question is related to computing what is called "invariant measure" for a particular well known fractal - the Sierpinski triangle.
We have an array m of four two by two matrices, say
...
6
votes
0answers
263 views
Increasing recursion speed in Hull-White trinomial tree calculation
First timer here and have been finding these boards very useful in learning Mathematica.
I'm trying to implement a numerical procedure for the Hull-White trinomial tree in Mathematica. Despite using ...
5
votes
3answers
443 views
recursive integration
I am trying to do multiple integrations recursively. For instance, I would like to do the following equation for arbitrary integer $n$:
$\displaystyle R_n(t) = \int_0^t \mathrm dt' R_0(t-t') ...
5
votes
4answers
180 views
Can the general term my recurrence equations be written with Floor or Mod?
I want to know the formula for the general term of the following recurrence system. I guess it can be written with Floor or Mod. ...
5
votes
1answer
71 views
5
votes
1answer
168 views
Build recursion in parallel?
Problem
Let's define a simple recursion.
f[1] = 1;
f[n_] := f[n] = f[n - 1]*n;
If I evaluate f in parallel
...
4
votes
2answers
115 views
Update a function avoiding infinite recursion
I am quite new to Mathematica and not completely familiar with functional programming. I am currently working with a function (call it foo) and wish to change its behaviour, for example, by adding 1 ...
4
votes
3answers
94 views
Modify this code using Module and While
I have written a recursive function and would like to re-write the code using Module AND While to compare the timings.
Here is my recursive function for f[n], where 6 n f[n] = f[n-1] + n! for n>0 and ...
4
votes
1answer
326 views
Polynomial Approximation from Chebyshev coefficients
I would like to expand a function $f(r)$ in the domain $[0,R]$, around the points $r =0$, and $r = R$ in the following manner
$f(r = 0) = \Sigma_{i=0,i = even}^{imax} f_i (r/R)^i$
and
$f(r = R) = ...
4
votes
1answer
88 views
RSolve gives a Context::ssle error
I want to solve the following recurrence equation
RSolve[{(k + 2) c[k + 2] q^(k + 1) - c[k] == 0}, c[k], k]
During calculation in Mathematica I get this ...
4
votes
1answer
245 views
How do I use RSolve to solve a system of recurrence relations?
I am trying to solve a system of recurrence relations as follows.
...
4
votes
1answer
196 views
Error Interpretation in NIntegrate
I am using a recursion algorithm developed by Migdal for Lattice Field Theory, and I have the following code:
...
4
votes
1answer
270 views
Solving recurrence relation using Mathematica defined in a piecewise way
I have a recurrence relation defined as following:
RSolve[
{
p[0] == p0,
p[1] == λ p[0]/μ,
p[i + 1] == λ p[i]/(2 μ)
},
p[i], i
]
Note that the relation ...
4
votes
1answer
384 views
Efficient backtracking with Mathematica
Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ...
4
votes
0answers
97 views
Speeding up multilinear PRA branch-and-bound algorithm with worst-case exponential time scenario with respect to basic events
The algorithm is a branch-and-bound algorithm that calculates dominances for PRA, probalistic risk assessment. The task was to find faster ways to do it in numerical software such as Matlab but we ...
3
votes
3answers
218 views
Implementing the Farey sequence efficiently
There is of course the silly implementation:
FareySequence[n_] := Union[Flatten[Table[j/i, {i, 1, n}, {j, 0, i}]]]
However, there are numerous properties and ...
3
votes
3answers
151 views
How to generate a recurrent sequence
How to generate this type of sequence?
$$ f(n, x) = x f'(n-1, x) \hspace{2 mm}, f(0, x) = e^x$$
How do I evaluate it for numerical values for $x = 1$ or any number?
3
votes
1answer
102 views
How to make a simple tree yourself with defined distances for each generation?
I'm trying to make a function that generates a tree for spin spin analysis in spectroscopy. I though it would be pretty easy, but I'm totally stocked.
The tree should look something like this:
...
3
votes
1answer
224 views
How to implement Condition programmatically?
I am writing my own symbolic functions with custom symbolic properties.
So often I wish to introduce some automatic simplifications or evaluations, which return the same head as it's argument. This ...
3
votes
1answer
78 views
Using NestWhileList to determine smallest prime value in series
I have a function recursively defined as follows:
$a_{n+1}-1=(a_n-1)\times lpf(a_n)$, whe $lpf(x)$ is the least prime factor of $x$.
Now, given an initial value of $a_0$, I would like to find the ...
3
votes
1answer
84 views
RecurrenceTable with vector
Mathematica can do a RecurrenceTable with a vector, here is a simple example:
RecurrenceTable[{x[n + 1] == 2* x[n], x[0] == {1, 2, 3}}, x, {n, 3}]
with output
...
3
votes
1answer
155 views
Avoid crash in recursive Dynamic
With the following Dynamic cell, I can reproducibly crash Mathematica, so do not try this unless you have saved all your work!
...
3
votes
1answer
450 views
Solve pair of recurrence relations
[Corrected equations and added simple example]
Can you solve a system of (loosely) coupled recurrence relations like this in Mathematica somehow?
...
3
votes
0answers
114 views
Solving recursion relations using Mathematica
I want to solve the recursion relation given in equation 2.7(a/b) on page $6$ of this paper. (..the initial seed is $F_1 = G_1 = 1$ and the functions $\alpha$ and $\beta$ are defined on page $5$ in ...
3
votes
0answers
76 views
An recurrence equation that can be solved in version 7 but not in version 8
A friend of mine showed me this code sample:
RSolve[{a[n] == a[n - 5] + 1, Sequence @@ Table[a[i] == 1, {i, 5}]}, a[n], n] // Timing
It's solved by version 7 in ...
2
votes
3answers
362 views
Recursive function on list
Please consider the following: I have to deliver the weekly customer demand data on time. I can start to produce my products one week in advance. So I was thinking ...
2
votes
2answers
67 views
Rising Recursion Relationships
Lets say I want to compute the following function in mathematica:
$G[n,k]=G[n+1,k-1] + G[n+2,k-2]$ where I know that $G[n,0]=n$ and $G[n,1]=n^2$.
So, for example, $G[3,2]=G[4,1]+G[5,0]=4^2+5$ or, ...
2
votes
2answers
241 views
defining recursively a function with multiple if conditions
I am trying to recursively define a function which satisfies the following system of equations and which depends on two parameters $n$ and $l$,
$$
\begin{align}
A(x, n, l) &= F[ A(x,n-1,l) ]\\
...
2
votes
2answers
92 views
Recursion doesn't happen any more or doesn't happen correctly if I store the recursive relationship in a variable first
I know the following code will form a recursion:
Clear["Global`*"]
u[i_, n_] := u[i - 1, n] + u[i, n - 1]
u[0, n_] := n
u[i_, 0] := i
u[2, 2]
(* => 8 *)
But ...
2
votes
2answers
236 views
How to define functions for a parameter-dependent recursive sequence
I am trying to generate a two variable recursive sequence
For instance on Mathematica, I did
z[1] := {1, 1}
B := {{t, 1}, {-1, t}}
z[n_, t_] := B.z[n - 1, t]
...
2
votes
1answer
73 views
Notation not recursive enough?
My notation is not recursing enough. For example,
Notation[W[a_ | b_] ⟹ foo[a_, b_]/foo[b_]]
Notation[W[a__, b_ | c_] ⟹ W[a__ | c_]W[b_ | c_]]
Then
...
2
votes
1answer
108 views
How can I get the general term of this recurrence equations?
Following is the recurrence relation:
a[1] = 1;
a[n_] := a[n - a[n - 1]] + 1
Array[a, 28]
I tried to use RSolve, but it ...
2
votes
1answer
70 views
Recursion depth exceeded
Below is my code for numerical solving of PDE with Crank Nicolson scheme.
...
2
votes
0answers
42 views
RSolve and incomplete gamma function
I am interested in how Mathematica uses the incomplete gamma function to solve difference equations. For example, if we have this inhomogeneous, 2nd order equation and use ...
2
votes
0answers
77 views
Nonlinear recurrence relation
I entered the following recurrence relation into RSolve and it just gave the question back to me. $$a_{n+1} = \frac{(1+a_n +(a_{n−1})^3)} 3$$
Is there another way to get a formula for the nth term?
2
votes
0answers
106 views
Am I entering this 2-variable recurrence correctly?
I'm trying to solve this recurrence with two variables.
...
1
vote
1answer
135 views
Differentiation w/o assiging concrete values
v = Subscript[v, 0]*Sin[(Pi*S)/Subscript[S, 0]];
a = dv/ds v;
a = D[v, s]
returns
...
1
vote
1answer
554 views
Defining a recursive sequence
I want to define a recursive sequence and then ask Mathematica to print a specific value:
Am I doing something wrong?
1
vote
1answer
152 views
Using different random values at each recursion step
I have the following code:
ϕ[0] := π/4
ϕ[n_] := Exp[-n] ϕ[n - 1] + Sqrt[1 - Exp[-2 n]] M
M = RandomVariate[NormalDistribution[0, 1]]
For this recursion relation, ...
