Head and Tail Recursion Comparison - Understanding Recursive Depth Limits

[joelb95]

Hi All,

I have two different recursion functions I am working on, but I don't know whether they make any difference to Excel's ability to handle them.  One is a normal recursive function and the other a tail recursive function.  Suffice it to say, both of them (in combination with some other somewhat irrelevant functions) will return at least 2,000 results, but it takes a long time to do that. Does anyone have any insights into why the two versions should perform similarly and why Excel starts to fall apart as the number count increases?  Weird things happen with the spilled arrays like vestiges of older values remaining in the space and having to be manually deleted (despite being "empty") prior to being able to spill the new results.  Try to ignore my data structures - just accept that they work as written and permit me to pass around discrete arrays/parameters.  The overall goal of the recursive functions is to aggregate discrete values/arrays for each iteration of a generator function (takes only a single integer parameter) for a range of values from 1 to n.

range.map.list =

lambda(

    encap_range_num_gen_func,

    let(

        num, encap.getfirstElement(encap_range_num_gen_func),

        gen_func, encap.getSecondElement(encap_range_num_gen_func),

        recursive_case,

            lambda(

                self,

                n,

                if(

                    n = 1,

                    list.create(stuff(gen_func(n))),

                    let(

                        recurse, self(self, n-1),

                        current, gen_func(n),

                        list.AddElement(encaptwo(recurse,current))

                    )

                )

            ),

        recursive_call, recursive_case(recursive_case, num),

        recursive_call

    )

);

range.map.list.tail =

lambda(

    encap_range_num_and_gen_func,

    let(

        num, encap.getfirstElement(encap_range_num_and_gen_func),

        gen_func, encap.getSecondElement(encap_range_num_and_gen_func),

        initial_accumulator_list, list.create(stuff(gen_func(1))),

        accumulate, lambda(acc, n, list.AddElement(encaptwo(acc,gen_func(n)))),

        accum_and_continue_or_accum_and_return,

            lambda(self, n, accumulator,

                if(

                    n>num,

                    accumulator,

                    self(self, n+1, accumulate(accumulator, n))

            )

        ),

        result,

        accum_and_continue_or_accum_and_return(accum_and_continue_or_accum_and_return, 2, initial_accumulator_list),

        result

    )

);

[#2]

@joelb95 

It seems like you're working with recursive functions in Excel and encountering performance issues as the number of recursive calls increases. Let's discuss the differences between head recursion and tail recursion and how they might impact Excel's ability to handle them efficiently.

1. Head Recursion:
• In head recursion, the recursive call is made before any other operations in the function.
• Each recursive call adds to the call stack, potentially leading to stack overflow errors if the recursion depth is too large.
• Excel's calculation engine may struggle with head recursion because it relies on a stack-based evaluation system, and a large number of recursive calls can quickly consume available stack space.
2. Tail Recursion:
• In tail recursion, the recursive call is the last operation performed in the function.
• Tail-recursive functions are optimized in many programming languages to use constant stack space, as the recursive call can be replaced with a loop-like structure that doesn't add to the call stack.
• However, Excel's calculation engine may not optimize tail-recursive functions in the same way, potentially leading to similar performance issues as head recursion if the recursion depth is too large.

Given these considerations, it's possible that both head and tail recursive functions may encounter performance issues in Excel, especially as the number of recursive calls increases. Excel's calculation engine may struggle with managing a large number of recursive calls due to limitations in stack space or other internal constraints.

To address the performance issues, you may need to reconsider the design of your recursive functions or explore alternative approaches that avoid excessive recursion. This could involve optimizing the algorithms to reduce the number of recursive calls, using iterative approaches instead of recursion, or leveraging Excel's built-in functions and features more effectively to achieve your desired results.Formularbeginn

Note: My knowledge of this topic is limited, but since no one has answered it, I entered your question in various AI. The text and the steps are the result of various AI's put together.

My answers are voluntary and without guarantee!

Hope this will help you.

Was the answer useful? Mark as best response and like it!

This will help all forum participants.

[#3]

@NikolinoDE 

Hi.  Thanks for the effort - I know it is a bit of an esoteric topic.  I am sort of surprised that there isn't more talk around recursion and introducing more advanced data manipulation into excel cells/arrays.