none
Strange behaviour of recursive function calls and stacks RRS feed

  • Question

  • I'm currently struggling with unwanted reordering of a stack during some recursive function calls.
    Basically, I'm trying to carry a stack of objects throught these recursive calls, but they end up being in the wrong order even after one level of recursion.

    The following is an outline of my script, just showing lines of code affecting the stack:

    function recurseStack 
    {
        [OutputType([Collections.Generic.Stack[string]])]
        param([Parameter(Mandatory=$true)]
                [Collections.Generic.Stack[string]]$stack)
        
        $string = $stack.Peek()
        if ($string -ne <Limit>)
        {
            $stack.Push($string + $string)
            $stack = recurseStack $stack
        }
        $stack
    }
    
    $stack = [Collections.Generic.Stack[string]]::new()
    $stack.Push("a")
    recurseStack $stack

    When running the script while <Limit> is "a" the output is the following:
    a

    When running the script while <Limit> is "aa" the output is the following:
    a
    aa

    When running the script while <Limit> is "aaaa" the output is the following:
    aaaa
    aa
    a

    When running the script while <Limit> is "aaaaaaaa" the output is the following:
    a
    aa
    aaaa
    aaaaaaaa

    When running the script while <Limit> is "aaaaaaaaaaaaaaaa" the output is the following:
    aaaaaaaaaaaaaaaa
    aaaaaaaa
    aaaa
    aa
    a

    ...and so on.

    Based on this the stack seems to be reordered during every call to the function.
    Problem is, I don't see why...

    EDIT:
    Interestingly, when assigning the function's return value to a new variable the output will be as expected in all cases:

    function recurseStack 
    {
        [OutputType([Collections.Generic.Stack[string]])]
        param([Parameter(Mandatory=$true)]
                [Collections.Generic.Stack[string]]$stack)
        
        $string = $stack.Peek()
        if ($string -ne <Limit>)
        {
            $stack.Push($string + $string)
            $newstack = recurseStack $stack
        }
        else
        {
            $newstack = $stack
        }
        return $newstack
    }
    
    $stack = [Collections.Generic.Stack[string]]::new()
    $stack.Push("a")
    recurseStack $stack
    I know that directly working with a provided parameter value is a bad habit and creation of a loca copy inside the function is advised, but I've certainly never encountered such strange behaviour caused by this "habit" before.
    • Edited by DMoenks Wednesday, July 27, 2016 9:59 AM
    Wednesday, July 27, 2016 9:22 AM

Answers

  • Hi Moenks,

    this is due to how Stacks work and the type of an already existing variable.

    When you assign the output of the nested call of recurseStack to a new variable, it will store this as a generic System.Object[] array and put the content of the stack in the correct order into it.

    However, if the variable already had a previous type, it will try to fit the output of the function into the existing type (which in case of a properly typed generic stack collection will work.

    Now add to this how PowerShell handles output of functions to facilitate pipeline: Collections are returned by passing one object from it after the other. In the case of your stack, this means the nested function call will return the stack in the top-to-down order one object after another. When the output is assigned to a stack-typed variable it will then add them in the same order, which means the first object out of the returned stack will be the first object put into the receiving stack.

    This causes the reordering you have observed.

    Cheers,
    Fred

    PS: In the second solution the stack is disolved into a regular array in the innermost nested call. When passing it down as an array it's an array-to-array storing each time, which does not have the Stack-behavior and thus maintains order.


    There's no place like 127.0.0.1

    • Proposed as answer by jrv Wednesday, July 27, 2016 2:14 PM
    • Marked as answer by DMoenks Thursday, July 28, 2016 6:56 AM
    Wednesday, July 27, 2016 1:13 PM

All replies

  • $stack.Push($string +$string) ????

    \_(ツ)_/


    • Edited by jrv Wednesday, July 27, 2016 12:52 PM
    Wednesday, July 27, 2016 12:51 PM
  • Hi Moenks,

    this is due to how Stacks work and the type of an already existing variable.

    When you assign the output of the nested call of recurseStack to a new variable, it will store this as a generic System.Object[] array and put the content of the stack in the correct order into it.

    However, if the variable already had a previous type, it will try to fit the output of the function into the existing type (which in case of a properly typed generic stack collection will work.

    Now add to this how PowerShell handles output of functions to facilitate pipeline: Collections are returned by passing one object from it after the other. In the case of your stack, this means the nested function call will return the stack in the top-to-down order one object after another. When the output is assigned to a stack-typed variable it will then add them in the same order, which means the first object out of the returned stack will be the first object put into the receiving stack.

    This causes the reordering you have observed.

    Cheers,
    Fred

    PS: In the second solution the stack is disolved into a regular array in the innermost nested call. When passing it down as an array it's an array-to-array storing each time, which does not have the Stack-behavior and thus maintains order.


    There's no place like 127.0.0.1

    • Proposed as answer by jrv Wednesday, July 27, 2016 2:14 PM
    • Marked as answer by DMoenks Thursday, July 28, 2016 6:56 AM
    Wednesday, July 27, 2016 1:13 PM
  • Good explanation.  That is why I pointed out that the objects are being re-added repeatedly as a hint as to where to look.

    Fred went the extra 50 miles.


    \_(ツ)_/

    Wednesday, July 27, 2016 2:14 PM
  • $stack.Push($string +$string) ????

    \_(ツ)_/



    That was just to have the function do something simple and have a visual representation of the effect.
    My actual function is more complex and would have been to long for a forum post.
    Thursday, July 28, 2016 6:56 AM