Ackermann function


 
Thread Tools Search this Thread
Top Forums Shell Programming and Scripting Ackermann function
# 1  
Old 03-07-2010
Ackermann function

Hi,
Do you konw how should Ackermann function look in bash or sh, or any diffrent shell laguage ??
I know this function i c++ but I don't know enough shell language

Thanks for any help
# 2  
Old 03-07-2010
Reference for those who don't know what the Ackermann function is:link
# 3  
Old 03-07-2010
I am assuming you are doing this to take a recursive algorithm that you know and learn more about shell scripting by rewriting in bash or sh?

Certainly you are not doing it for performance ;-}

There is a group of Ackermann functions written in many different languages here:

Ackermann's Function

The closest to shell form would be the Perl version.

That looks like this:

Code:
#!/usr/bin/perl
use strict;
use integer;

sub Ack {
    my($M, $N) = @_;
    return( $N + 1 )         if ($M == 0);
    return( Ack($M - 1, 1) ) if ($N == 0);
    Ack($M - 1, Ack($M, $N - 1));
}

my $NUM = $ARGV[0];
$NUM = 1 if ($NUM < 1);
my $ack = Ack(3, $NUM);
print "Ack(3,$NUM): $ack\n\n";

Translating that to BASH is straightforward:

Code:
#!/bin/bash

#Uncomment the 'set' if you want a line-by-line result...
#set -x   

ack ()
{
	local m=$1
	local n=$2
	if [ $m -eq 0 ] 
	   then
		return $(( $n+1 )) 
	fi

	if [ $n -eq 0 ] 
	   then
		ack $(( $m-1 )) 1
		return $?
	fi
	
	ack $m $(( $n-1 ))
	ack $(( $m-1 )) $? 
}
loops=0
p=$1
o=3
(( num = p<1?1:$p ))

ack $o $num 
printf "ack %s %s = %s  \n\n" $o $num $?

There is a problem, however, with the BASH version (or any of sh, bash, etc). The return value from a subroutine or a script is 8 bits. So the ack function can only be used on really small values. It is the same as the Perl up to an input value of 4, but then produces '254' which is the largest direct return value from a subroutine. To fix that, I will leave that as an exercise to the reader...

Last edited by drewk; 03-08-2010 at 12:42 PM.. Reason: typos...
# 4  
Old 03-09-2010
Ok. As an exercise, I have:
Code:
#!/bin/bash

function ack
{
  local m=$1 n=$2

  if ((m == 0)); then let r=n+1
  elif ((n == 0)); then ack $((m-1)) 1
  else
    ack $m $((n-1))
    ack $((m-1)) $r
  fi
}               
        
ack $1 $2
echo "ack($1, $2) =" $r

# 5  
Old 03-10-2010
Great answer!

Last edited by drewk; 03-10-2010 at 11:27 AM.. Reason: edited out wrong info...
Login or Register to Ask a Question

Previous Thread | Next Thread

10 More Discussions You Might Find Interesting

1. Shell Programming and Scripting

Function - Make your function return an exit status

Hi All, Good Day, seeking for your assistance on how to not perform my 2nd, 3rd,4th etc.. function if my 1st function is in else condition. #Body function1() { if then echo "exist" else echo "not exist" } #if not exist in function1 my all other function will not proceed.... (4 Replies)
Discussion started by: meister29
4 Replies

2. Shell Programming and Scripting

Need help on awk for printing the function name inside each function

Hi, I am having script which contains many functions. Need to print each function name at the starting of the function. Like below, functionname() { echo "functionname" commands.... } I've tried like below, func=`grep "()" scriptname | cut -d "(" -f1` for i in $func do nawk -v... (4 Replies)
Discussion started by: Sumanthsv
4 Replies

3. Shell Programming and Scripting

Will files, creaetd in one function of the same script will be recognized in another function?

Dear All. I have a script, which process files one by one. In the script I have two functions. one sftp files to different server the other from existing file create file with different name. My question is: Will sftp function recognize files names , which are created in another... (1 Reply)
Discussion started by: digioleg54
1 Replies

4. Shell Programming and Scripting

Passing variable value in a function to be used by another function

Hello All, I would like to ask help from you on how to pass variable value from a function that has been called inside the function. I have created below and put the variables in " ". Is there another way I can do this? Thank you in advance. readtasklist() { while read -r mod ver... (1 Reply)
Discussion started by: aderamos12
1 Replies

5. Shell Programming and Scripting

Help to Modify File Name in each function before calling another function.

I have a script which does gunzip, zip and untar. Input to the script is file name and file directory (where file is located) I am reading the input parameters as follows: FILENAME=$1 FILEDIR=$2 I have created 3 functions that are as follows: 1) gunzip file 2) unzip file... (2 Replies)
Discussion started by: pinnacle
2 Replies

6. Programming

How to step in one function after the function be executed in gdb?

In gdb, I can call one function with command "call", but how can I step in the function? I don't want to restart the program, but the function had been executed, gdb will execute next statement, and I don't know how to recall the function. (4 Replies)
Discussion started by: 915086731
4 Replies

7. Shell Programming and Scripting

After exit from function it should not call other function

Below is my script that is function properly per my conditions but I am facing one problem here that is when one function fails then Iy should not check other functions but it calls the other function too So anyone can help me how could i achieve this? iNOUT i AM GIVING TO THE... (1 Reply)
Discussion started by: rohit22hamirpur
1 Replies

8. Shell Programming and Scripting

SHELL SCRIPT Function Calling Another Function Please Help...

This is my function which is creating three variables based on counter & writing these variable to database by calling another function writeRecord but only one record is getting wrote in DB.... Please advise ASAP...:confused: function InsertFtg { FTGSTR="" echo "Saurabh is GREAT $#" let... (2 Replies)
Discussion started by: omkar.sonawane
2 Replies

9. Shell Programming and Scripting

Return a value from called function to the calling function

I have two scripts. script1.sh looks -------------------------------- #!/bin/bash display() { echo "Welcome to Unix" } display ----------------------------- Script2.sh #!/bin/bash sh script1.sh //simply calling script1.sh ------------------------------ (1 Reply)
Discussion started by: mvictorvijayan
1 Replies

10. Shell Programming and Scripting

Passing global variable to a function which is called by another function

Hi , I have three funcions f1, f2 and f3 . f1 calls f2 and f2 calls f3 . I have a global variable "period" which i want to pass to f3 . Can i pass the variable directly in the definition of f3 ? Pls help . sars (4 Replies)
Discussion started by: sars
4 Replies
Login or Register to Ask a Question