7 ms·

People are talking about logic gates and computing. While these things are associated with electric circuits, strictly speaking, they don't have to be. It's sor

People are talking about logic gates and computing. While these things are associated with electric circuits, strictly speaking, they don't have to be. It's sort of a separate domain all together. For something strictly an electric circuit that uses recursion take a look at an op-amp: https://en.wikipedia.org/wiki/Operational_amplifier https://en.wikipedia.org/wiki/Operational_amplifier. Normal operation of an op amp basically involves a feedback loop which is the analog equivalent of recursion. Basically anything with a feedback loop is recursion.

elevaet 4y ago
Resonant filters, like the classic Moog ladder filter, are another great example of recursive/feedback circuit designs. As someone coming from a computing background, it always seems magical how the recursion in these types of analogue circuits happens instantaneously.
- raverbashing 4y ago
  > how the recursion in these types of analogue circuits happens instantaneously. Yeah, theoretically instantaneous, in practice not. (There's a measure for that but I can't remember how's it called) Even funnier that the feedback actually increases the bandwidth of the system, compared to the open loop amplifier.
  - Cloudly 4y ago
    >There's a measure for that but I can't remember how's it called Slew rate for opamps I believe Also worth noting that the "recursion" without negative feedback will hit a limit when the op-amp is saturated. Similar to a "stack overflow" I guess. Things mostly won't break but you'll get a flat output at the positive or negative rails of the op-amp - which causes some of the pain of analog signal processing.
  - hex4def6 4y ago
    >Even funnier that the feedback actually increases the bandwidth of the system, compared to the open loop amplifier. The reason for this is because of how bandwidth is defined, which is basically the point at which the amplifier gain starts dropping the higher the frequency you go. Adding feedback is effectively clipping the low frequency/ high gain area with the net effect that the gain versus frequency plot is a lot flatter (but now, instead of being able to get say 10,000x gain at 1Hz, you're clipping it to 100x, since you're unable to get 10,000x at 1Mhz)
- Gordonjcp 4y ago
  It's not recursive. To be recursive you'd have to be able to unwind some sort of memory to get all previous states.
  - viraptor 4y ago
    I don't think that's required for recursion. You only need access to as many previous states as you need for the result, but not all. We often talk about tail recursion optimisation where the stack never grows.
  - dustingetz 4y ago
    the unwinding property comes from the stack; see tail recursion
  - fnordpiglet 4y ago
    You can implement binary search recursively, which doesn’t care about the stack just the final iteration. I don’t see where the stack unwinding is necessarily for “call the same function inside itself unless you’re done” except in cases where the stack is used to compute a final answer that’s based on the prior iterations. Maybe it’s fair to say those would best be implemented iteratively, but it’s unnecessary that they be.
- IIAOPSW 4y ago
  No matter how hard I try, I can't get this stupid snake to stop eating itself!
exDM69 4y ago
I will respectfully disagree about opamp feedback loops being recursion. It is almost magical but I do not see any recursive nature in it. You can't compute fib(n) recursively with O(1) transistors. Maybe if you use the non-recursive exponentiation formula. Analog electronics is different from digital computation because it's not about inputs and outputs, cause and effect in the same manner. A circuit maintains an equilibrium between inputs and outputs. The input doesn't cause the output as the changing the output may affect the input. Just a simple resistor is an example: is voltage or current the input to Ohm's law? Neither is. Same with the opamp feedback loop. It looks like it feeds its output to the input and then repeats. But it doesn't, it just maintains the same relationship between them by pumping electrons from the power supply. Short circuit the output to ground and you will see the circuit load the input circuit more. That said opamp circuits are very cool. The patent for negative feedback was rejected as "another perpetual motion machine". Yet it works and it works magically. A (bad) opamp can be cobbled together from 4 or 5 transistors. Yet it can do, together with negative feedback: addition, subtraction, multiply by constant, integral, derivative, exponent and logarithm. Probably others too. Combine log, add, and exp and you have a multiplier. But it won't do a Fibonacci, a factorial or the Ackermann function. There is no way I am aware of that could compute anything of recursive nature with a constant number of parts. You need some form of memory ("space") and a method of repeating the same computation ("time") to qualify. You certainly can build this kind of computer with digital, or even analog, circuits. But negative feedback in opamps is not it. This is my contribution to the Sunday morning semantics debate on the nature of recursive computation.
- jojobas 4y ago
  With a delay line and an opamp adder you can in fact sort of loop-compute fib(n). It won't be recursion though, more like a direct forward loop.
- artemonster 4y ago
  Feeding own output to own inputs IS a definition of a recursion
  - atoav 4y ago
pjc50 4y ago
Feedback systems are iteration, not recursion: you can't go backwards. (Tail recursion is I suppose recursion that only goes forwards and is considered equivalent to iteration?)
- naasking 4y ago
  Iteration+state is equivalent to recursion. Simple feedback circuits can probably do primitive recursion, and for more powerful form of loops/recursion, you probably need to add stateful elements.
azubinski 4y ago
"anything with a feedback loop is recursion" No. Recursion and feedback are absolutely different concepts.
- dustingetz 4y ago
  i am trying to untangle the semantics of recursion/iteration/loop/feedback scientifically (that’s why i posted this link); do you have any sources?
  - kilgnad 4y ago
    https://en.m.wikipedia.org/wiki/Recursion https://en.m.wikipedia.org/wiki/Recursion Anything that can be defined in terms of itself is recursion. This is the official definition and an opamp fits here. A lot of people are getting lost in the variations of the semantics like computer recursion vs. analog recursion. I think the first sentence in the Wikipedia article, however, cinches the the general concept. Yes anything with a feedback loop is recursion because a system with feedback is a system defined in terms of itself. But these things in the end are semantic illusions. We are wasting huge amounts of effort in defining the boundaries of the definitions behind meaningless symbols. Does the definition of banana encompass a rotten banana? Is something that has been rotted or digested... Is that still a banana? Who cares. Words are just used for communication. If your point was expressed properly without the need to clearly specify exact semantic definitions then I would just leave it at that.

elevaet 4y ago

Resonant filters, like the classic Moog ladder filter, are another great example of recursive/feedback circuit designs. As someone coming from a computing background, it always seems magical how the recursion in these types of analogue circuits happens instantaneously.

raverbashing 4y ago
> how the recursion in these types of analogue circuits happens instantaneously. Yeah, theoretically instantaneous, in practice not. (There's a measure for that but I can't remember how's it called) Even funnier that the feedback actually increases the bandwidth of the system, compared to the open loop amplifier.
- Cloudly 4y ago
  >There's a measure for that but I can't remember how's it called Slew rate for opamps I believe Also worth noting that the "recursion" without negative feedback will hit a limit when the op-amp is saturated. Similar to a "stack overflow" I guess. Things mostly won't break but you'll get a flat output at the positive or negative rails of the op-amp - which causes some of the pain of analog signal processing.
- hex4def6 4y ago
  >Even funnier that the feedback actually increases the bandwidth of the system, compared to the open loop amplifier. The reason for this is because of how bandwidth is defined, which is basically the point at which the amplifier gain starts dropping the higher the frequency you go. Adding feedback is effectively clipping the low frequency/ high gain area with the net effect that the gain versus frequency plot is a lot flatter (but now, instead of being able to get say 10,000x gain at 1Hz, you're clipping it to 100x, since you're unable to get 10,000x at 1Mhz)
Gordonjcp 4y ago
It's not recursive. To be recursive you'd have to be able to unwind some sort of memory to get all previous states.
- viraptor 4y ago
  I don't think that's required for recursion. You only need access to as many previous states as you need for the result, but not all. We often talk about tail recursion optimisation where the stack never grows.
- dustingetz 4y ago
  the unwinding property comes from the stack; see tail recursion
- fnordpiglet 4y ago
  You can implement binary search recursively, which doesn’t care about the stack just the final iteration. I don’t see where the stack unwinding is necessarily for “call the same function inside itself unless you’re done” except in cases where the stack is used to compute a final answer that’s based on the prior iterations. Maybe it’s fair to say those would best be implemented iteratively, but it’s unnecessary that they be.
IIAOPSW 4y ago
No matter how hard I try, I can't get this stupid snake to stop eating itself!

exDM69 4y ago

I will respectfully disagree about opamp feedback loops being recursion. It is almost magical but I do not see any recursive nature in it. You can't compute fib(n) recursively with O(1) transistors. Maybe if you use the non-recursive exponentiation formula. Analog electronics is different from digital computation because it's not about inputs and outputs, cause and effect in the same manner. A circuit maintains an equilibrium between inputs and outputs. The input doesn't cause the output as the changing the output may affect the input. Just a simple resistor is an example: is voltage or current the input to Ohm's law? Neither is. Same with the opamp feedback loop. It looks like it feeds its output to the input and then repeats. But it doesn't, it just maintains the same relationship between them by pumping electrons from the power supply. Short circuit the output to ground and you will see the circuit load the input circuit more. That said opamp circuits are very cool. The patent for negative feedback was rejected as "another perpetual motion machine". Yet it works and it works magically. A (bad) opamp can be cobbled together from 4 or 5 transistors. Yet it can do, together with negative feedback: addition, subtraction, multiply by constant, integral, derivative, exponent and logarithm. Probably others too. Combine log, add, and exp and you have a multiplier. But it won't do a Fibonacci, a factorial or the Ackermann function. There is no way I am aware of that could compute anything of recursive nature with a constant number of parts. You need some form of memory ("space") and a method of repeating the same computation ("time") to qualify. You certainly can build this kind of computer with digital, or even analog, circuits. But negative feedback in opamps is not it. This is my contribution to the Sunday morning semantics debate on the nature of recursive computation.

jojobas 4y ago
With a delay line and an opamp adder you can in fact sort of loop-compute fib(n). It won't be recursion though, more like a direct forward loop.
artemonster 4y ago
Feeding own output to own inputs IS a definition of a recursion
- atoav 4y ago

pjc50 4y ago

Feedback systems are iteration, not recursion: you can't go backwards. (Tail recursion is I suppose recursion that only goes forwards and is considered equivalent to iteration?)

naasking 4y ago
Iteration+state is equivalent to recursion. Simple feedback circuits can probably do primitive recursion, and for more powerful form of loops/recursion, you probably need to add stateful elements.

azubinski 4y ago

"anything with a feedback loop is recursion" No. Recursion and feedback are absolutely different concepts.

dustingetz 4y ago
i am trying to untangle the semantics of recursion/iteration/loop/feedback scientifically (that’s why i posted this link); do you have any sources?
- kilgnad 4y ago
  https://en.m.wikipedia.org/wiki/Recursion https://en.m.wikipedia.org/wiki/Recursion Anything that can be defined in terms of itself is recursion. This is the official definition and an opamp fits here. A lot of people are getting lost in the variations of the semantics like computer recursion vs. analog recursion. I think the first sentence in the Wikipedia article, however, cinches the the general concept. Yes anything with a feedback loop is recursion because a system with feedback is a system defined in terms of itself. But these things in the end are semantic illusions. We are wasting huge amounts of effort in defining the boundaries of the definitions behind meaningless symbols. Does the definition of banana encompass a rotten banana? Is something that has been rotted or digested... Is that still a banana? Who cares. Words are just used for communication. If your point was expressed properly without the need to clearly specify exact semantic definitions then I would just leave it at that.