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
580 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
320 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
615 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
170 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
5answers
191 views
Wrapping a function in count
I am working through the Programming Paradigms via Mathematica (A First Course) and am attempting to answer the following:
Use recursion to count how many times the argument can have its square
...
8
votes
4answers
182 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
271 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
198 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
219 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
4answers
233 views
Partitioning a list by recursion (Programming Paradigms via Mathematica (A First Course))
I am working through the course Programming Paradigms via Mathematica. One of the homework exercises for the section Recursion I: Passing the Buck is as follows:
Use recursion to partition a ...
6
votes
1answer
278 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
277 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
495 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
187 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
74 views
5
votes
1answer
171 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
125 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
103 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
94 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
340 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
262 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
203 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
274 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
406 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
101 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
234 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
156 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
106 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
228 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
88 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
157 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
459 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
122 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
78 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
376 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
70 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
271 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
95 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
259 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
74 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
110 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
84 views
Recursion depth exceeded
Below is my code for numerical solving of PDE with Crank Nicolson scheme.
...
2
votes
0answers
44 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
84 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
110 views
Am I entering this 2-variable recurrence correctly?
I'm trying to solve this recurrence with two variables.
...
1
vote
1answer
138 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
...
