# How can I use a For loop in a recursive function?

I am creating a simple radix2 FFT algorithm (based on Cooley-Turkey) by using a recursive function to obtain the fft. The function is supposed to work on a list (assuming the length is a power of two). and it's supposed to give back a list of the same size. The code I wrote gives back a single output. It looks like the For loop is not working. Would anybody know why the For loop is not working?

Clear[fft2]
fft2[L_] :=
fft2[L] = Module[{Le, Lo, n, w, k}, (*Rememeber previous step*)
n = Length[L];
If[n == 1, (*Tests if N=1 and assigns that value if true*)
L,
Le = Take[L, {1, -1, 2}]; (*Creates a new list of size N/2 with even indexed elements*)
Lo = Take[L, {2, -1, 2}]; (*Creates a new list of size N/2 with odd indexed elements*)
For[k = 0, k < n, k++, (*Combines terms*)
w = Exp[-2 Pi I *k/n];
Xk = fft2[Le] + w*fft2[Lo];
Return[Xk]
]
]
]
-
your loop doesnt get past k=0 since it immediately hits Return – george2079 Apr 16 '14 at 0:27
thank you @george2079, I modified it using AppendTo. I start with an empty list and then store the values in it from the loop then I ask to return the value after the loop. This gives me a list inside a list it seems.'For [k = 0, k < n, k++, w = Exp[-2 [Pi] I k/n]; Xk = fft2[Le] + wfft2[Lo]; fourier = AppendTo[list, Xk]; ]; Return[fourier]; ] ] – Vianey Apr 19 '14 at 2:44
fft2[L_] := fft2[L] = Module[{Le, Lo, n, w, Xk, fourier = {}},(*Rememeber previous step*) n = Length[L]; If[n == 1,(*Tests if N=1 and assigns that value if true*) L, Le = Take[L, {1, -1, 2}]; Lo = Take[L, {2, -1, 2}]; For [k = 0, k < n, k++, w = Exp[-2 \[Pi] I *k/n]; Xk = fft2[Le] + w*fft2[Lo]; fourier = AppendTo[fourier, Xk]; Print["fourier inside the loop ", k, " ", fourier]; Print["n is ", n];]; Return[fourier]; ]] – Vianey Apr 19 '14 at 4:43