AWK 的递归调用失败？

Question

我正在尝试实现 Wikipedia 中定义的快速排序的简单变体。然而，在我看来，旧的递归调用中的局部变量会泄漏到以后的调用中。 （我目前的解释。）。是这样吗？有什么解决方法吗？

这是示例代码

# Quick sort - Simple variant. Requires 0(n) extra store 
# Divide and conquer. Pick a pivot, compare elements to
# pivot generating two sublists; one greater than pivot 
# and the other less than pivot. Sort these two recursively.
# See http://en.wikipedia.org/wiki/Quicksort#Simple_version

function dump_array(arr_arg){

        arr_arg_len = length(arr_arg)
        RSEP = ORS;
        ORS=" ";
        dctr = 1; 
        # Do not use length(arr_arg) in place of arr_arg
        # It fails. The following doesn't work
        #while (dctr <= arr_arg_len){
        while (dctr <= arr_arg_len){
                print arr_arg[dctr]; 
                dctr++;
        }; 
        ORS = RSEP;
        print "\n";
}


function simple_quicksort(unsorted_str)
{

        # Unpack from the str - space separated
        print "******************************"
        print "Called with "unsorted_str
        # Split the space separated string into an array
        split(unsorted_str, unsorted_array, " ");

        array_len = length(unsorted_array);

        # No more sorting to be done. Break recursion
        if (array_len <= 1){
                print "Ending recursion with "unsorted_str
                return unsorted_str
        }
        # Pick a random value as pivot
        # index must not be 0
        idx = 0
        while (idx == 0){
                srand()
                idx = int(rand() * array_len)
        }
        pivot = unsorted_array[idx]
        if (debug >= 1){
                print "idx:"idx" pivot is: "pivot
        }

        num = 1;
        # we don't use the zero'th element,
        # this helps us declare an empty array
        # dunno any other method
        # we'll remove it anyway
        less_arr[0] = 0
        less_ctr = 1
        more_arr[0] = 0
        more_ctr = 1
        while (num <= array_len){ 
                # Skip pivot
                if (idx != num){
                        if (unsorted_array[num] <= pivot){
                                if (debug >= 1){
                                        print "Element less than pivot: "unsorted_array[num]
                                }
                                less_arr[less_ctr] = unsorted_array[num]
                                less_ctr++;
                        }else{
                                if (debug >= 1){
                                        print "Element more than pivot: "unsorted_array[num]
                                }
                                more_arr[more_ctr] = unsorted_array[num]
                                more_ctr++;
                        }
                }
                num++
        };
        # strip out the holder in idx 0
        delete less_arr[0]
        delete more_arr[0]
        if (debug >= 1){
                print "Less than pivot:"
                print dump_array(less_arr)
                print "More than pivot:"
                print dump_array(more_arr)
        }

        # Marshal array back to a string
        less_str=""
        less_length = length(less_arr)
        num = 1
        print "Less length: "less_length
        while (num <= less_length){
                less_str = less_str" "less_arr[num]     
                num++;
        }

        # same thing for more
        more_str=""
        more_length = length(more_arr) 
        num = 1
        while (num <= more_length){
                more_str = more_str" "more_arr[num]
                num++;
        }

        if (debug >= 1){
                print "Going for a recursive call with elements < pivot: "less_str
                print "Going for a recursive call with elements > pivot: "more_str
                print "pivot was: "pivot
        }

        # Tried to delete the local variables
        # Coz it seems like local vars are visible to recursed functions
        # Is this why it fails?
        delete less_arr
        delete more_arr
        delete unsorted_array
        print "^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"
        print ""

        return simple_quicksort(less_str) " "pivot" "simple_quicksort(more_str)


}

BEGIN{
        print "-- quick sort --"
}

{
        # print the unsorted objects
        print "Unsorted "NF" objects:\n"$0; 

        # We'll use a slightly different method,
        # Pass the $0 string to the sorter, let it split
        # it into an array, qsort that array, generate sub- 
        # strings and recursively qsort them

        #Simple version
        sorted = simple_quicksort($0)

}

END{
        print "Sorted "NF" objects"; 
        print "Sorted >>"sorted
}

示例运行：

echo 5 12 7 2 13719 28019 21444 30578 30647 | awk -f devel/andorian-blog/awk/sorting/quick_sort.awk -v debug=1
-- quick sort --
Unsorted 9 objects:
5 12 7 2 13719 28019 21444 30578 30647
******************************
Called with 5 12 7 2 13719 28019 21444 30578 30647
idx:1 pivot is: 5
Element more than pivot: 12
Element more than pivot: 7
Element less than pivot: 2
Element more than pivot: 13719
Element more than pivot: 28019
Element more than pivot: 21444
Element more than pivot: 30578
Element more than pivot: 30647
Less than pivot:
2 


More than pivot:
12 7 13719 28019 21444 30578 30647 


Less length: 1
Going for a recursive call with elements < pivot:  2
Going for a recursive call with elements > pivot:  12 7 13719 28019 21444 30578 30647
pivot was: 5
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

******************************
Called with  2
Ending recursion with  2
******************************
Called with  12 7 13719 28019 21444 30578 30647
idx:1 pivot is: 12
Element less than pivot: 7
Element more than pivot: 13719
Element more than pivot: 28019
Element more than pivot: 21444
Element more than pivot: 30578
Element more than pivot: 30647
Less than pivot:
7 


More than pivot:
13719 28019 21444 30578 30647 


Less length: 1
Going for a recursive call with elements < pivot:  7
Going for a recursive call with elements > pivot:  13719 28019 21444 30578 30647
pivot was: 12
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

******************************
Called with  7
Ending recursion with  7
******************************
Called with  13719 28019 21444 30578 30647
idx:3 pivot is: 21444
Element less than pivot: 13719
Element more than pivot: 28019
Element more than pivot: 30578
Element more than pivot: 30647
Less than pivot:
13719 


More than pivot:
28019 30578 30647 


Less length: 1
Going for a recursive call with elements < pivot:  13719
Going for a recursive call with elements > pivot:  28019 30578 30647
pivot was: 21444
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

******************************
Called with  13719
Ending recursion with  13719
******************************
Called with  28019 30578 30647
idx:1 pivot is: 28019
Element more than pivot: 30578
Element more than pivot: 30647
Less than pivot:



More than pivot:
30578 30647 


Less length: 0
Going for a recursive call with elements < pivot: 
Going for a recursive call with elements > pivot:  30578 30647
pivot was: 28019
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

******************************
Called with 
Ending recursion with 
******************************
Called with  30578 30647
idx:1 pivot is: 30578
Element more than pivot: 30647
Less than pivot:



More than pivot:
30647 


Less length: 0
Going for a recursive call with elements < pivot: 
Going for a recursive call with elements > pivot:  30647
pivot was: 30578
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

******************************
Called with 
Ending recursion with 
******************************
Called with  30647
Ending recursion with  30647
Sorted 9 objects
Sorted >> 2 5  7 12  13719 21444  28019  30578  30647

该运行看起来不错。与下一张比较一下：

$ echo 5 12 7 2 13719 28019 21444 30578 30647 | awk -f devel/andorian-blog/awk/sorting/quick_sort.awk -v debug=1  
-- quick sort --
Unsorted 9 objects:
5 12 7 2 13719 28019 21444 30578 30647
******************************
Called with 5 12 7 2 13719 28019 21444 30578 30647
idx:6 pivot is: 28019
Element less than pivot: 5
Element less than pivot: 12
Element less than pivot: 7
Element less than pivot: 2
Element less than pivot: 13719
Element less than pivot: 21444
Element more than pivot: 30578
Element more than pivot: 30647
Less than pivot:
5 12 7 2 13719 21444 


More than pivot:
30578 30647 


Less length: 6
Going for a recursive call with elements < pivot:  5 12 7 2 13719 21444
Going for a recursive call with elements > pivot:  30578 30647
pivot was: 28019
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

******************************
Called with  5 12 7 2 13719 21444
idx:4 pivot is: 2
Element more than pivot: 5
Element more than pivot: 12
Element more than pivot: 7
Element more than pivot: 13719
Element more than pivot: 21444
Less than pivot:



More than pivot:
5 12 7 13719 21444 


Less length: 0
Going for a recursive call with elements < pivot: 
Going for a recursive call with elements > pivot:  5 12 7 13719 21444
pivot was: 2
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

******************************
Called with 
Ending recursion with 
******************************
Called with  5 12 7 13719 21444
idx:3 pivot is: 7
Element less than pivot: 5
Element more than pivot: 12
Element more than pivot: 13719
E    lement more than pivot: 21444
Less than pivot:
5 


More than pivot:
12 13719 21444 


Less length: 1
Going for a recursive call with elements < pivot:  5
Going for a recursive call with elements > pivot:  12 13719 21444
pivot was: 7
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

******************************
Called with  5
Ending recursion with  5
******************************
Called with  12 13719 21444
idx:2 pivot is: 13719
Element less than pivot: 12
Element more than pivot: 21444
Less than pivot:
1    2 


More than pivot:
21444 


Less length: 1
Going for a recursive call with elements < pivot:  12
Going for a recursive call with elements > pivot:  21444
pivot was: 13719
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

******************************
Called with  12
Ending recursion with  12
******************************
Called with  21444
Ending recursion with  21444
******************************
Called with  21444
Ending recursion with  21444
Sorted 9 objects
Sorted >> 2  5 7  12 13719  21444 13719  21444

Answer 1

在 AWK 中，您在函数中引用的所有变量都是全局变量。不存在“局部变量”这样的东西。
然而，AWK 中的函数参数的行为类似于局部变量，因为它们在调用嵌套或递归函数时被“隐藏”。
因此，您只需获取函数中的所有“局部变量”并将它们添加为函数的额外参数即可。
当您调用该函数时，您可以省略这些额外的参数。
通常在参数和“局部变量”之间放置一些额外的空格，以便记录您的函数应该如何使用。
此行为和约定记录在 GAWK 文档：函数定义语法。