Recursive Calculations

[SurferNate]

I am relatively new to database development and find that I have dived into it head first with a full major project in the works already. While I've learned a huge amount in only 13 months, I discover almost daily that I am lacking some critical understanding required to make further progress and refinements.

Recently I discovered the power of recursive calculations, however, I am struggling with the logic required to actually write them. Is there somewhere I can get a sound and easy to understand tutorial on writing recursive calcs?

Or, maybe, I'm even lacking in an inderstanding of what a recursive calc actually IS...

Thanks in advance!

Nathan

[Ender]

The only way to really get a recursive calc is to use a custom function. You need FM7 Developer or FM8 Advanced to add and edit custom functions. But they can be a big help with certain types of problems.

If you have FM7 Developer, or FM8 Advanced, or you just want to learn more about the power of custom functions, check out the discussions, samples, and resources in the Custom Functions forum.

[Ender]

Hey, how'd that happen? My references to "custom function" have all turned into URLs!

Stephen, have you been adding new tricks to the forums again?

[comment]

The only way to really get a recursive calc is to use a custom function.

You can do recursions in a [spoilerq:1]repeating[/spoilerq] calculation field, too. And, of course, in a script.

[spoilera:1][color:violet]Just kidding![/spoilera]

[LaRetta]

AND you can do pseudo-recursion within Let()

HAH!!! I thought your 'repeating' was like the 'custom function' issue - just turning into a link because of the name. I expected it to jump me to a section instead of displaying spoiler!!

God, I needed humor today! Thanks! :giggle:

Edited December 14, 2005 by Guest

[comment]

Why sure, go ahead and give it away...

Like [spoilerq:1]this[/spoilerq] is not bad enough.

[spoilera:1]YOU CAN SEE THE SPOILER IN RECENT POSTS![/spoilera]

[SurferNate]

Thanks for the links etc. I know that custom functions are how recursion is pulled off. I have Dev7 and am working in Pro8 now. I cannot justify 8Advanced just yet but I'm trying.

My real question was to get a schoolbook understanding of recursion. ie. start with understanding the simplest recursive function possible and then add a complexity etc. I looked on the web but found mostly technical articles for "real" programmers that do not relate the basic mathematical concept in a way that I can wrap my head around. Of course I can sort of hack and modify others' pre-developed functions, in fact I have, but that's script kiddie stuff. I'm looking for sound primary theory (something in which I'm sorely lacking)upon which to build. I'm missing WHY and HOW it really works.

[SlimJim]

One of the fundamental methods of proof in mathmematics is called Mathematical Induction and recursion is closely linked to induction. You may get more internet hits at a basic level if you look for both induction and recursion.

A starter is the page on recursion at answers.com

http://www.answers.com/topic/recursion

[Ender]

The idea is to take a complex problem and progressively reduce it, handling one part at a time. With each iteration of the function, you solve one part, then call the same function sending the remaining part of the problem as the parameter(s). Eventually, the problem will reduce, and there will be nothing left to evaluate.

Some recursive functions complete the computations at each iteration, and pass the result of each step to the next function call, others hold onto the value at each step until all successive results are resolved and returned (this is called tail recursion.)

A simple example is an exponent function, where x is multiplied by itself y times.

exponent ( x ; y ) =

case ( y > 1 ;

x * exponent ( x ; y -1 );

1 )

So for x = 3, y = 4, you can see how the problem is broken down:

exponent ( 3, 4 ) =

3 * exponent ( 3, 3 ) =

3 * (3 * exponent ( 3, 2 )) =

3 * (3 * (3 * exponent ( 3, 1 ))) =

3 * (3 * (3 * (3 * 1))) =

3 * (3 * (3 * 3)) =

3 * (3 * (9)) =

3 * (3 * 9) =

3 * (27) =

3 * 27 =

81

That was a tail recursion example. There are many more examples, and different ways to break a problem down (iterative, divide and conquer.) More on the general theory can be found on the Internet or in algorithm texts. Hopefully that gives you the general idea.

[comment]

This may seem a bit pedestrian in view of the above, but...

If you understand looping scripts, you understand recursive calculation. In fact, Filemaker's custom_function* is more primitive than a looping script.

---

(*) I think I found a way around that automatic link, finally.

[Ender]

I think I found a way around that automatic link, finally.

Hee, hee, I use two spaces: custom function!

[SurferNate]

Thanks guys,

I DO understand looping scripts, I use them all the time. I've even got one I'm quite proud of to evaluate a user action that walks them through a decision process. (sort of a decision tree that loops back to a logical point if the user suddenly decides they are headed in the wrong direction)

The fact of thinking about a function that contains itself is like a mental Escher drawing. Ender gave me what I was looking for. Something so primitive that I can actually write it out and work it backwads and forwards. Manually producing the result of at least the first couple recursions is a big help because I can see the way the parameters are passed and what the result is. Just like relational theory, I'm slowly forming a mental picture of the logic.

[SurferNate]

HOORAY!!!

I think I've got it! I disassembled one of Ray's less complicated recursive functions. Here's the breakdown.

Let([

W = Length(SourceText);

X = Length(SearchText);

Y = Left(SourceText; X);

Z = If(Y = SearchText; X; 1)];

If( X > 0 and Y = SearchText ;

TextColor ( TextStyleAdd (Y ; Bold );RGB ( R ; G ; B ));

Left(SourceText; 1))

&

If( X > 0 and W > 0;

Hilite(Right(SourceText; W - Z); SearchText; R; G; B );

Right(SourceText; W - 1)

)

)

//case-transparent hilite function by Ray Cologon

//www.nightwing.com.au/FileMaker

/* EXAMPLE RESULT

hilite(apples;ples)

W=6

X=4

Y=appl

Z=1

FIRST IF = a

&

SECOND IF =

hilite(pples;ples)

W=5

X=4

Y=pple

Z=1

FIRST IF = p

&

SECOND IF =

hilite(ples;ples)

W=4

X=4

Y=ples

Z=4

FIRST IF = TextFormat(ples)

&

SECOND IF =

hilite("";ples)

W=0

X=4

Y=""

Z=1

FIRST IF = ""

&

SECOND IF = ""

END OF LOOP BECAUSE hilight WAS NOT CALLED THIS LAST TIME. W=0 AND hilite ONLY RESULTS INSIDE THE EQUATION IF W>0.

*/