How To Fix an Infinite Recursion?

Asked by Sarah Chesbrough

Sarah Chesbrough (view profile)

on 10 Nov 2018
Latest activity Commented on by Walter Roberson

Walter Roberson (view profile)

on 12 Nov 2018
function z=fft_do(x,T)
N=156;
T=5;
dt=T/N;
f0=12.8;
f1=12;
t =(1:N)*dt;
fft_do(sin(2*pi*f0*(t))+2*sin(2*pi*f1*(t)));
% or
%fft_do(sin(2*pi*30*(1:128)/128*5),5);
N=length(x);
%dt=T/N;
X=fft(x,N);
N2=floor(N/2);
Power=X.*conj(X)/N^2;
f=(0:N2)/(N2*2*dt);
z=Power;
stem(f,2*Power(1:N2+1))
xlabel('Frequency')
ylabel('Power')
title('Power spectral density')

Sarah Chesbrough

Sarah Chesbrough (view profile)

on 11 Nov 2018
I am still unsure about what you mean when you say stopping conditions. Yes their are two input arrays; T for time and x which is a given sine function. It is really confusing that both the
fft_do(sin(2*pi*30*(1:128)/128*5))
and
fft_do(sin(2*pi*30*(1:128)/128*5),5)
work when I type them in the command window but not when I run them as a script.
Any insight on how to get that line of code to work in the script?
Stephen Cobeldick

Stephen Cobeldick (view profile)

on 11 Nov 2018
"I am still unsure about what you mean when you say stopping conditions"
A recursive function must have a stopping condition which tells the recursion to terminate, otherwise it will just continue calling itself forever or throw an error when it runs out of data. For example a recursive function that processes a graph or tree and the stopping condition is when it reaches the end of that data, i.e. there is no more data in the graph/tree to parse.
If you are not sure what stopping conditions are and how to specify them then use the internet. When I used [major internet search engine] to search for "tutorial recursive function stopping condition" I got more than 6 million results, and this was the very first one:
Look at some examples and explanations. It will help you to understand how recursive functions work and how they need to be specified.
Walter Roberson

Walter Roberson (view profile)

on 12 Nov 2018
Classical recursive functions work by dividing problems into pieces. One of the approaches (less common) is to grab a small piece of the problem, calculate that, and then if anything is left to call recursively to do the rest of the problem. The more common approach is to check to see if the problem is small enough to solve trivially and if so solve it, and otherwise to pull off most of the problem and ask to recursively solve it, and then use the result together with the little bit that remains to calculate the solution. Mathematically these two approaches are equivalent assuming commutative operations. In these two approaches, each time a recursive call is made, a smaller problem is being sent to be solved, so you can be sure that at some point you will get down to a trivial problem that you can solve. (Note: mathematically it is permitted to recurse submitting problems that are tough to solve, where it might take some hard mathematics to prove that the calculations will definitely end, even if most of the time they end relatively quickly. Recursion can be hard to prove, but in practice most of the time it is used in situations where the proof is easy.)
An example of the two different strategies: suppose you have a list of numbers to add. You can break that down as:
1. If input list has only one element, return it, otherwise return the first element plus the recursive sum of the remaining elements; or
2. if input list is only one element return it and otherwise return the recursive sum of all but the last element, plus the last element
These two correspond to
A+(B+(C+(D+....
and
((((A+B)+C)+D)+....
respectively. These are the right to left summation and the left to right summation, which are mathematically equivalent if you have indefinite precision.
So the question for you is what the subproblem is to be solved at each point. If you have an input that is 16 elements long, can you break the task up into solving a 15 element task and combining that with the one element? Perhaps you can break it up into solving two 8 elements tasks and solving those and combining the results?
The classic original FFT algorithm did rely upon the inputs being powers of two long, and breaking the input into halves, doing the calculations for the halves, and recombination with "butterfly" patterns . So there is distinct potential for recursive calculations. It gets messier if the inputs are not powers of two in length but there is recursion available based upon lengths that factor the input length.