5
\$\begingroup\$

Can an electric circuit do recursion?

By recursion I mean any kind of recursion, tail, binary, nested, etc: http://www.sparknotes.com/cs/recursion/whatisrecursion/section2.rhtml

By electric circuit I mean a simple board without any special chips, just wires, resistors, diodes, capacitors etc.

\$\endgroup\$
  • 5
    \$\begingroup\$ I guess feedback could be thought of as a kind of recursion... but "recursion" is an algorithmic construct, a circuit isn't. \$\endgroup\$ – Majenko Mar 9 '15 at 11:51
  • \$\begingroup\$ What is a "special chip" ? I would think that anything that involves feedback would be considered recursive. \$\endgroup\$ – efox29 Mar 9 '15 at 11:51
  • \$\begingroup\$ @efox29 a programmable microchip for example or a CPU, stuff you can't make at home. \$\endgroup\$ – shinzou Mar 9 '15 at 11:55
  • \$\begingroup\$ @Majenko so in general it's impossible to have algorithms in simple circuits? \$\endgroup\$ – shinzou Mar 9 '15 at 11:56
  • 2
    \$\begingroup\$ @kuhaku Also, a CPU is just a large collection of transistors. With enough patience (and transistors) you can make one at home. Google "Homebrew CPU with Transistors" \$\endgroup\$ – Majenko Mar 9 '15 at 12:05
8
\$\begingroup\$

First we need to decide what recursion really is. When you take a recursive function, there may exist a transformation that gets rid of the recursion, but introduces state. In other cases, the transformation will have to introduce both state and iteration. So, writing a function out recursively is a way of making state and possibly iteration implicit, as opposed to explicit. In other words, recursion is just a way of writing out the thing.

The state is there anyway, you're just not explicitly putting it down on paper. In languages such as C, recursive function calls usually store their state on the stack.

Now, any circuit that has state (stored charge, energy, etc.) - and that will be all of them, really - is, by definition, recursive. No iteration necessary :)

Concretely, let's work on a first-order IIR filter. Its output can be given by a recursive function. Given an input signal x(t), the output y(x(t), t) = a1*y(x(t-1), t-1) + b0*x(t), where a1 and b0 are constants that parametrize the response. This is in discrete time - t is an integer with the unit of a number of clock cycles.

The C implementation, assuming t>=0 and x(-1) == 0, would be:

float a1, b0;

// Recursive, Implicit State
float y(float (*x)(int), int t) {
  return t != 0 ? a1 * y(x(t-1), t-1) + b0 * x(t) : b0 * x(t);
}

// Non-Recursive, Explicit State
float y(float (*x)(int), int t) {
  static float y_prev = 0.0;
  if (1) { // optional to ensure correct use only
    static int t_prev = 0;
    assert(t_prev == t-1 || t == 0);
  }
  return y_prev = a1 * y_prev + b0 * x(t);
}

The code can be also be implemented as a first order switched-capacitor infinite impulse response filter. You can certainly build such a system:

schematic

simulate this circuit – Schematic created using CircuitLab

SW1 flips twice in each clock cycle. With values shown, for 12 bit accuracy the clock is limited to 10kHz due to R4-C1 time constant. U1, U2, U3 are voltage followers - say op-amps configured for gain=1.

If we set a1=(1-b0), and transform this to a continuous time differential equation, we can get the "same" (continuous) response with an RC circuit:

schematic

simulate this circuit

Here, T is the clock period of the clock feeding the switched capacitor circuit above, and U1 is a voltage follower.

When the frequencies of interest are limited to ~1/10th of the clock frequency, both the continuous-time and the discrete-time (switched capacitor) circuits respond the same.

Both circuits, and the code, can be modeled by a recursive function, also known as a recurrence relation.

\$\endgroup\$
  • 1
    \$\begingroup\$ If one could balance two capacitors perfectly, and had switches with no parasitic capacitance, series resistance, leakage, or other unwanted effects, one could build an arbitrary-precision DAC which would accept signals in LSB-first format. For each step, charge an "input" cap to VDD or ground, then connect it to the output cap. The most singificant bits of the output voltage after some number of steps will be the last few bits clocked to the device. Of course, practical considerations would limit useful precision to far less than that of a conventional DAC, but the concept is still cute. \$\endgroup\$ – supercat Mar 9 '15 at 16:39
  • \$\begingroup\$ @supercat AFAIK, a vacuum-isolated circuit (or even an air-isolated one) could have precise capacitors, and balancing them to 1ppm using an impedance bridge is not extraordinarily hard. You could probably do it just fine in the 60s at the latest. As for the switch, you don't need a capacitance-free device, just a constant-capacitance device. I think that a 16-bit DAC could be demonstrated that way, using air capacitors and a mechanically-actuated switch. With a few tiny dielectric spacers, made of a good material, between the large plates, their dielectric absorption could be kept at bay. \$\endgroup\$ – Kuba Ober May 14 at 22:03
9
\$\begingroup\$

What that page calls "linear recursive" can be done to some extent in hardware, where it's called successive approximation. The example of Newton-Raphson is a good one as it's quite close to how analogue gun director computers worked.

But generally it's a bad idea to adapt programmer's intuition (based around executing a series of instructions) to electronic circuits (based around continuous flow).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.