PDA

View Full Version : Recursive Call



hcrisp
02-03-2009, 08:54 AM
How many times can a function recursively call itself? Is this documented anywhere?



FUNCTION myfunction, x, DEPTH=depth, MAX_LEVELS=max
IF depth LE max THEN BEGIN
x = x + 1.
x = myfunction(x, DEPTH=depth+1L, MAX_LEVELS=max)
ENDIF
RETURN, x
END

rwagner
02-04-2009, 02:39 PM
This really begs the question... why are you asking? Did you blow the stack or just curious? I'll try some tests out on a couple of machines, but none of our developers are aware of a hard-coded limit to stack levels...

hcrisp
02-04-2009, 02:50 PM
I would like to know what is a "safe limit" that I can expect to recursively call and not have problems. On my machine, I empiricially found that I can call up to 464 times before it goes up in smoke. Can I expect this level of recursion on other machines?

It's not just curiosity since recursion is a very effective way to code certain functions. Factorial, for example, or a nearest neighbor search. If I can't use recursion, or if I can't add code to ensure it stays within same limits, I will have to find a better way to write the algorithm.

Cheers

ed
02-04-2009, 03:57 PM
An interesting challenge. Testing your code on my rather formidable desktop running Vista 64, I can only reach max=239. On my lesser laptop running 32-bit XP, I can reach max=389. Both are running Wave 9.01. I expected the limit to be much higher for a 64-bit machine and am a little surprised. It isn't immediately apparent what the limit depends on.

rwagner
02-06-2009, 09:03 AM
Trying this on my XP32 desktop (big beefy machine) I get a max level of 388.
On a bigger linux machine I get 4483.
On the same machine running wave64 I get 2809.

While recursion is obviously an extremely powerful tool which makes code more elegant etc... I feel it's place is more in the world of C and lower level languages as opposed to our high level interpreted language. Just as we try to dissuade our users from writing too many for loops in their code for performance reasons, I think we may have to try and avoid deeply nested recursions for stability reasons.

Many times when WAVE users are writing nested for loops or deep recursions in a function they are unaware of built-in wave functionalities that can accomplish the same task while increasing performance and stability. If you have any specific questions regarding how to accomplish this (you mentioned nearest neighbor as an example?), please feel free to ask!

hcrisp
02-06-2009, 09:26 AM
Okay, I found an efficient way to do factorials:



; Want to find 4!, i.e. the factorial of 4
WAVE> PRINT, exp(total(alog(findgen(4)+1)))


A nearest neighbor search involves first setting up a kd-tree with this kind of process: http://en.wikipedia.org/wiki/Kd-tree (See Python code)

Basically I need to find a way to:
1) Start with an N-length array
2) Find the middle element, and save it
3) take the array elements from the left side of the middle element and repeat this process until there are no more than one element per side
4) take the array elements from the right side of the middle elements and repeat this process until there are no more than one element per side

Is there a slick way to do this in WAVE?

rwagner
02-10-2009, 04:11 PM
Hi Hcrisp, I started playing with some slick ways of indexing to make your kd tree, but I got sidetracked. I'll try to have some examples posted soon!