For questions about defining recursive functions, recursive algorithms and solving recursive equations.

learn more… | top users | synonyms

47
votes
2answers
9k views

How can I use Mathematica's graph functions to cheat at Boggle?

Boggle is a word game played with 16 dice and a 4x4 tray. This question is inspired by a Stack Overflow question about Boggle that I decided to solve using Mathematica. In addition to Mathematica, I ...
36
votes
4answers
2k 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 ...
24
votes
3answers
871 views

Smooth Peter de Jong attractor

Today I was playing with Peter de Jong attractor. At the bottom of the page I've linked there are beautiful examples like: My attempts are not so great: It is around 10^5 points. For more than ...
24
votes
4answers
1k 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 ...
22
votes
7answers
619 views

Alternative ways to implement a triangular recursion

Triangular recursions are a class of algorithms that frequently turn up in computational mathematics. These recursions are expressible in the general form ...
21
votes
3answers
970 views

Visualisation of a recursive function

Is there a way to nicely visualize recursive functions? (diagrams/plots) More specifically I'm looking for a way to make contrast (visually) between e.g. the cosine function which if continuously ...
17
votes
3answers
707 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 ...
14
votes
6answers
536 views

How can I evaluate only a single step of a recursive function?

Let's say have a simple recursive function for the Fibonacci sequence f[0] := 1 f[1] := 1 f[n_] := f[n - 1] + f[n - 2] but I want to see how it will expand in a ...
11
votes
7answers
2k 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) & ...
11
votes
7answers
391 views

Concatenation of lists in a Fibonacci-like pattern

I am trying to create a List of elements that follow the general pattern: $$X_{n+1} = X_n X_{n-1}$$ where the operation on the right hand side is concatenation, i.e., joining. I want to achieve the ...
11
votes
3answers
237 views

ToExpression fails with long nested string expressions

Consider the following conversion from String to Mathematica Expression: ...
11
votes
2answers
1k 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}$. ...
10
votes
5answers
589 views

How to deal with recursion formula in Mathematica?

In engineering problems, I am always seeing many recursion formula. For instance, In the book "The NURBS book", I discovered many recursion formula Fibonacci ...
10
votes
4answers
293 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 ...
10
votes
2answers
403 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 ...
9
votes
2answers
327 views

Recursive Integral for Volume of $n$-Ball

The volume of an $n$-ball (the $(n+1)$-dimensional analogue of a disk) of radius $r$ can be found by the following integral recurrence: $$V_0(r)=2r$$ ...
9
votes
2answers
225 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 ...
9
votes
1answer
673 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 ...
8
votes
4answers
417 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 ...
8
votes
3answers
426 views

Create sine function with random increase in phase

I am trying to simulate a signal that randomly increases its phase, so far I have tried two thing but neither worked. I usually use matlab but I want to learn some Mathematica so I thought I would try ...
8
votes
5answers
281 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
2answers
294 views

Recursive partitioning: Is there a better way to do this?

Consider the following function, which recursively splits a list into equal length sublists (the length of the list is assumed to be a power of the second argument): ...
8
votes
1answer
296 views

How can I define a Listable function only apply to a vector?

Consider the function f which should behave as f[{{1, 2}, {3, 4}, {5, 6, 7}}] ...
7
votes
2answers
76 views

Recursive function with array of variables

I am trying to create a recursive function which works with an increasing array of variables. Since the formula is quite complex, i will try to simplify my example to the core of my problem. The ...
7
votes
2answers
179 views

Solving with DSolve recursively

I need to find $f(x,n)$ in the interval [0,1] defined by recursion, \begin{equation} \frac{d f(x,n+1)}{dx} = f(x,n) \end{equation} with boundary conditions $f(0,n+1) = 1$ and $f(x,0)=1+ x $ Using ...
7
votes
2answers
376 views

How can I define a sequence of functions?

I need to define a function fun, and then re-define this function iteratively. The code is given at the end. First, a function ...
7
votes
1answer
286 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 ...
7
votes
1answer
955 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 ...
7
votes
1answer
108 views

How to find a recurrence relation for a sequence?

I have a sequence given by an explicit formula for n-th term: ...
7
votes
1answer
145 views

Recurrences of lists

Assume we have a multi-dimensional recurrence, e.g. $\qquad\begin{align*} a_1 &= (1,2) \\ a_n &= (1,2) + a_{n-1} \quad, n>1 \end{align*}$ with the easy solution $a_n = (n,2n)$. How ...
7
votes
0answers
266 views

Compile recursive function modifying global variables

How to compile recursive formula when it relies on more than a few global variables (global to the topmost compiled function)? It is unreasonable to pass on all such variables to each recursive ...
6
votes
5answers
259 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
302 views

What is the most elegant way to specifiy a start case for recursion?

When writing recursive code that computes the least value at which a condition is true and various other scenarios it is often necessary to specify a base case. What I have done to supply this is ...
6
votes
3answers
269 views

Nested list to graph

The following nested list can be regarded as a representation of a (tree) graph: ...
6
votes
1answer
248 views

Speeding up the non-negativity algorithm for multilinear function with interval probabilities?

The algorithm is a branch-and-bound algorithm that calculates the non-negativity of a multilinear function with interval probabilities. The lines 9-11 has an optimization that is explained on the ...
6
votes
0answers
416 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
764 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
2answers
567 views

Variable that changes itself

I am trying to store a boolean value into a variable with the additional property that the value changes each time the variable is called. ...
5
votes
3answers
547 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 ...
5
votes
2answers
284 views
5
votes
2answers
185 views

Plotting two recursive functions

I'm trying to plot two recursive functions (p and θ) on a map. So far I have: ...
5
votes
1answer
188 views

How can I make a “self-referential” replacement operation self-contained?

Fairly often I find use for replacement rules that call themselves on the right-hand side of the rule, e.g.: ...
5
votes
1answer
220 views

How to deal with too much recursion

I have put together a very simple climate model based around four equations which define the state at time t based on time t-1, ...
5
votes
2answers
228 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 ...
5
votes
4answers
257 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
3answers
416 views

Solving recurrence sequence using an ODE

I'm trying to solve the recurrence a[n] == 0 for n < l a[l] == 1 a[n] == (l + 2(n - l) a[n - l] + (n - l)(n - 1) a[n - 1])/n(n - l + 1) for n >= l using ...
5
votes
1answer
867 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) = ...
5
votes
1answer
221 views

Setting $RecursionLimit crashes Mathematica 10

I have encountered what I shall presume is a bug: setting $RecursionLimit repeatably crashes the Mathematica 10 kernel: ...
5
votes
1answer
151 views

How can I use a recursive function in a Module

I have a question about using a recursive function in a module. I made the following example to illustrate the question. The followwing code works: ...
5
votes
1answer
69 views

Specifying Range of RSolve

When I input RSolve[{0 == q[n + 1]^2 + 3 q[n + 1] + 2 q[n + 1] q[n] - 6 q[n] + q[n]^2, q[0] == 1}, q[n], n] I get two complicated-looking complex solutions: ...