Login or Register to Ask a Question and Join Our Community


Shell Programming and Scripting

Recursive function and arrays

Login to Discuss or Reply to this Discussion in Our Community

 
Thread Tools Search this Thread
Top Forums Shell Programming and Scripting Recursive function and arrays
# 1  
Old 02-10-2010
Recursive function and arrays
I have the following function in a bash script that fails to return the sorted array. I think the problem lies in the recursion not correctly passing the arrays, but I can't tell what I'm doing wrong. Anyone see the problem?

Code:
function quicksort () {
    local array=( `echo "$1"` )
    local -a l
    local -a g
    local x=
    if [ ${#array[@]} -lt 2 ]; then
        echo ${array[@]}
    else
      local pivot=${array[0]}
      for x in ${array[@]}; do
          echo "$x, $pivot"
          if [ $x -lt $pivot ]; then
              l=( ${l[@]} $x )
          else 
              g=( ${g[@]} $x )
          fi
      done
      echo `quicksort "$l"` $pivot `quicksort "$g"`
    fi
}

# 2  
Old 02-10-2010
Quote:
Originally Posted by tkg
I have the following function in a bash script that fails to return the sorted array. I think the problem lies in the recursion not correctly passing the arrays, but I can't tell what I'm doing wrong. Anyone see the problem?

Code:
function quicksort () {


The POSIX syntax for defining functions is quicksort() <compound command>.

The ksh syntax is function quicksort <compound command>.

What you are using is a hybrid that works only in bash (and, I think perhaps in zsh).
Quote:
Code:
    local array=( `echo "$1"` )


What do you expect in $1? Why are you using echo?
Quote:
Code:
    local -a l
    local -a g
    local x=
    if [ ${#array[@]} -lt 2 ]; then
        echo ${array[@]}
    else
      local pivot=${array[0]}
      for x in ${array[@]}; do
          echo "$x, $pivot"
          if [ $x -lt $pivot ]; then
              l=( ${l[@]} $x )
          else 
              g=( ${g[@]} $x )
          fi
      done
      echo `quicksort "$l"` $pivot `quicksort "$g"`
    fi
}

# 3  
Old 02-11-2010
Quote:
The POSIX syntax for defining functions is quicksort() <compound command>.

The ksh syntax is function quicksort <compound command>.

What you are using is a hybrid that works only in bash (and, I think perhaps in zsh).
Yes, I'm using bash. I tried the POSIX version as well, to see if it made any difference.

Quote:
Code:
local array=( `echo "$1"` )

What do you expect in $1? Why are you using echo?
$1 should contain the array passed to the function. I found this method searching the web. Is there a better method?

I suspect the problem may be related to this since when it descends to the first recursion level, the array length is seen as 1 and the function exits, returning only three numbers from the array. A check of $l and $g just prior to passing them to the recursive call shows them as they should be, so I'm not sure what the problem is.
# 4  
Old 02-11-2010
Quote:
Originally Posted by tkg
Yes, I'm using bash. I tried the POSIX version as well, to see if it made any difference.

It will only make a difference if you try to use the script in a different shell.
Quote:
$1 should contain the array passed to the function.

What do you mean by "the array"? Do you mean the name of the array? The elements of the array?
Quote:
I found this method searching the web. Is there a better method?

There's a lot of nonsense on the web.

If you want to pass the name of the array and then populate array with its elements, use:
Code:
local -a array
eval "array=( \"\${$1[@]}\" )"

Quote:
I suspect the problem may be related to this since when it descends to the first recursion level, the array length is seen as 1 and the function exits, returning only three numbers from the array. A check of $l and $g just prior to passing them to the recursive call shows them as they should be, so I'm not sure what the problem is.
# 5  
Old 02-11-2010
Quote:
There's a lot of nonsense on the web.
True enough.

Quote:
What do you mean by "the array"? Do you mean the name of the array? The elements of the array?
The elements. I tried the code you suggested and I get a "bad substitution" error. The original one I used does populate the "array" variable correctly, however. At least on the first pass.
# 6  
Old 02-11-2010
Quote:
Code:
local array=( `echo "$1"` )


That is the same as:
Code:
local array=( $1 )

...but much slower. Command substitution is slow.
Quote:
Code:
echo `quicksort "$l"` $pivot `quicksort "$g"`


Here you are not passing the entire array; "$l" or "$g" is only the first element of the array. To pass the full array:
Code:
echo `quicksort "${l[*]}"` $pivot `quicksort "${g[*]}"`

# 7  
Old 02-12-2010
I figured it out.
I had a logic error in the partitioning loop that would send one of the branches into an endless loop. Smilie\ Using '*' instead of '@' worked also, although I don't fully understand why yet. Here's my final code and thanks for all your help. I learned a lot, which was the point after all.
Code:
quicksort () {
	local -a array=( $1 )
	local -a l
	local -a g
	if [ ${#array[@]} -lt 2 ]; then
		echo ${array[@]}
	else
	  pivot=${array[0]}
	  for x in ${array[@]}; do
		  if [ $x -lt $pivot ]; then
			  l=( ${l[@]} $x )
		  elif [ $x -gt $pivot ]; then
			  g=( ${g[@]} $x )
		  fi
	  done
	  echo `quicksort "${l[*]}"` $pivot `quicksort "${g[*]}"`
	fi
}
Login or Register to Ask a Question

Previous Thread | Next Thread

10 More Discussions You Might Find Interesting

1. Programming

recursive function

Hello forum members, Please wirte a sample program for print the 1 - 100 and 100 -1 using recursive function. Thanks & regards Siva Rangnanath (2 Replies)
Discussion started by: workforsiva
2 Replies

2. Shell Programming and Scripting

Run recursive function with variables over SSH

Hi, I don't know if you can help or if this is even possible, but I am trying to run the following function over an ssh and (depending on the itteration I choose) keep getting unexpected token or undefined symbol errors. The function is: killtree() { typeset parent=$1 typeset child... (1 Reply)
Discussion started by: RECrerar
1 Replies

3. Shell Programming and Scripting

perl recursive function issue

I am facing some problem in perl recurssive function function my @array_parent = (Some inegers); my $outputfile = 'output.txt'; my $master_file = 'master.txt'; open (MASTER,"$>>master.txt"); foreach my $child (@array_parent){ my $line = `grep "$child" "$outputfile"`; ... (1 Reply)
Discussion started by: pritish.sas
1 Replies

4. Shell Programming and Scripting

AWK Problem in recursive function

Hi, I have a file like this SPF_HC00001|iCalcular_Monto_Minimo|--->|SPF_HC00028|pstcObtener_Monto_Minimo SPF_HC00004|iCalcular_Incrementos|--->|SPF_HC00032|pstcObtener_Num_Incrementos SPF_HC00005|iCalcular_Articulo_167_Reformado|--->|SPF_HC00031|pstcObtener_Por_CB_Inc... (2 Replies)
Discussion started by: kcoder24
2 Replies

5. Shell Programming and Scripting

Not able to store the results of perl recursive function when applied under for loop

Hi Perl Gurus , need URGENT HELP PLEASE !!!!! I have one recursive Perl function which takes path of any directory as argument and returns array containing all the sub folders inside it recursively. Now the problem is that it works well if i use it with one time but the problem is that when... (0 Replies)
Discussion started by: anthriksh2000
0 Replies

6. Shell Programming and Scripting

Recursive function in unix

Can someone tell me, how do i write a recursive code using shell ( eg like 'for' loop in C) which outputs the record to a database table as one row per iteration? (7 Replies)
Discussion started by: goutam_igate
7 Replies

7. Shell Programming and Scripting

Recursive function call problem

This is shell script I have made to lists out directory contents and filenames for any given directory (without using ls command). There is some problem in dirfunc function call which I have marked 1 is not working. Can anybody suggest what is the problem there and how should I correct it. ... (2 Replies)
Discussion started by: netresearch
2 Replies

8. Shell Programming and Scripting

Problem with Recursive function

Hi all, I have to move all the files in a tree directory structure to a single directory. Inorder to know which file is from which directory , i'll have to add the name of the directory to the file name. For this i wrote a recursive function which is as follows... (4 Replies)
Discussion started by: malle
4 Replies

9. Programming

recursive function

Hi everyone, i need your input on this. We can express a function recursivly like this A(n) = (2 n = 0 5 n = 1 A(n − 1) + A(n − 2) % 47 n > 1 How would i go about constructing a recursive function for this?... (1 Reply)
Discussion started by: bebop1111116
1 Replies

10. Shell Programming and Scripting

shell: creating different arrays based on function argument

hi, I was wondering if there was a good way to create an array within a function, where the name is based on a passed argument? I tried this: _____________________________ func(){ #take in 1st arg as the arrayname arrayName=$1 let i=0 while read line do arrayName=${line} let i+=1... (5 Replies)
Discussion started by: nix21
5 Replies
Login or Register to Ask a Question