How do I write a simple recursion function in bash and use its return value?

9 views
Skip to first unread message

gnuist

unread,
Dec 14, 2012, 7:29:13 PM12/14/12
to
Hi All,

How do I write a simple recursion function in bash and use its return
value?

Here is my attempt at a Fibonacci, the file name is
Fibinnaci
so I use for function, one more i
Fibinnacii


you see a lot of comment outs as there was problem with returning and
also syntax, whether to use expr `.........` or $((..........))

For readability, I prefer to use the function name than $0 cryptic,
which nevertheless refers to the shell script name, not function name.

please clarify the tradeoff between RETURN and ECHO also.

Any help would be APPRECIATED !!!


function Fibinnacii { # ( number n ) eg ( 5 )
local n; n=$1;
local out;
if [ $n -le 1 ] ; then
# return 1;
echo "1"
else
# out=` $(( Fibinnacii $(( $n - 1 )) )) + $(( Fibinnacii $(( $n -
2 )) )) ` ;
# return $out
# echo $(( $( Fibinnacii $(( $n - 1 )) ) + $( Fibinnacii $(( $n -
2 )) ) )) ;
# out=`expr \` Fibinnacii 1 \` + 1 ` ;
out=`expr \` Fibinnacii $n - 1 \` + 1 ` ;
echo $out
# return "5";
# echo 5
fi
}


out=`Fibinnacii 3` ;

echo $out





David W. Hodgins

unread,
Dec 14, 2012, 8:27:34 PM12/14/12
to
On Fri, 14 Dec 2012 19:29:13 -0500, gnuist <gnui...@hotmail.com> wrote:

> How do I write a simple recursion function in bash and use its return
> value?

See http://www.tldp.org/LDP/abs/html/recurnolocvar.html

Regards, Dave Hodgins

--
Change nomail.afraid.org to ody.ca to reply by email.
(nomail.afraid.org has been set up specifically for
use in usenet. Feel free to use it yourself.)

Janis Papanagnou

unread,
Dec 15, 2012, 12:12:13 AM12/15/12
to
On 15.12.2012 01:29, gnuist wrote:
> Hi All,
>
> How do I write a simple recursion function in bash and use its return
> value?
>
> Here is my attempt at a Fibonacci, the file name is
> Fibinnaci
> so I use for function, one more i
> Fibinnacii
>
>
> you see a lot of comment outs as there was problem with returning and
> also syntax, whether to use expr `.........` or $((..........))
>
> For readability, I prefer to use the function name than $0 cryptic,
> which nevertheless refers to the shell script name, not function name.

(No idea what you're asking here. - Just name the file containing the
function with the same name as teh function if you like.)

>
> please clarify the tradeoff between RETURN and ECHO also.

With 'return' don't expect that you can pass values larger than 127;
function return values are for passing exit status to the caller, not
for returning mathematical function values.

>
> Any help would be APPRECIATED !!!

function fib
{
n=${1:?}
if (( n == 0 ))
then printf 0
elif (( n == 1 ))
then printf 1
else
f1=$( fib $(( n-1 )) )
f2=$( fib $(( n-2 )) )
printf $(( f1 + f2 ))
fi
}

printf "%s\n" $( fib $1 )


But note two things; first, bash is slooow (compare, e.g., with ksh)

$ time ksh fib.sh 20
6765

real 0m0,43s
user 0m0,43s
sys 0m0,00s

$ time bash fib.sh 20
6765

real 0m21,54s
user 1m37,18s
sys 0m12,15s

and, second, a recursive solution for fibonacci will quickly get
extremely slow with any shell for any larger parameter value; you
should store already calculated values in an array and access those
instead of calling a function.

Janis

Marc Girod

unread,
Dec 16, 2012, 10:51:01 AM12/16/12
to
On Dec 15, 5:12 am, Janis Papanagnou <janis_papanag...@hotmail.com>
wrote:

> But note two things; first, bash is slooow (compare, e.g., with ksh)

Maybe use Perl, then...

> and, second, a recursive solution for fibonacci will quickly get
> extremely slow with any shell for any larger parameter value; you
> should store already calculated values in an array and access those
> instead of calling a function.

Good advice:

#!/usr/bin/perl -w

use strict;
no warnings 'recursion';
use bigint;
my %fib;
sub fib {
my $i = shift;
return 0 if $i < 1;
return 1 if $i == 1;
return $fib{$i} if $fib{$i};
return $fib{$i} = fib($i-1) + fib($i-2);
}
print fib($ARGV[0] || 0);

$ time ./fib 20
6765
real 0m0.212s
user 0m0.000s
sys 0m0.156s
$ rep name /proc/cpuinfo
model name : Intel(R) Celeron(R) CPU 540 @ 1.86GHz

Marc
Reply all
Reply to author
Forward
0 new messages