RECURSION - Java Programming: From Problem Analysis to Program Design - page 903

(Ackermann's Function) Ackermann's function is defined as follows:

11.

8
< n þ 1 ; if m ¼ 0

A ð m 1 ; 1 Þ; if n ¼ 0
A ð m 1 ; A ð m ; n 1 ÞÞ; otherwise ;

A ð m ; n Þ¼

:

where m and n are nonnegative integers. Write a recursive function to
implement Ackermann's function. Also write a program to test your func-
tion. What happens when you call the function with m ¼ 4andn ¼ 3?
12. Write a recursive method to implement the recursive definition of Exercise
14 (reversing the elements of an array between two indices). Also, write a
program to test your method.
13. Write a recursive method to implement the recursive definition of Exercise
15 (multiply two positive integers using repeated addition). Also, write a
program to test your method.

In the Decimal to Binary Conversion programming example presented in
this chapter, you learned how to convert a decimal number into its equiva-
lent binary number. Two more number systems, octal (base 8) and hex-
adecimal (base 16), are of interest to computer scientists.
The digits in the octal number system are 0 , 1 , 2 , 3 , 4 , 5 , 6 , and 7 . The
digits in the hexadecimal number system are 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , A , B ,
C , D , E , and F . So, A in hexadecimal is 10 in decimal, B in hexadecimal is 11
in decimal, and so on.
The algorithm to convert a positive decimal number into an equivalent
number in octal (or hexadecimal) is the same as that discussed for binary
numbers. Here, we divide the decimal number by 8 (for octal) and by 16
(for hexadecimal). Suppose that a b represents the number a to the base b.
For example, 75 10 means 75 to the base 10 (that is, decimal), and 83 16
means 83 to the base 16 (that is, hexadecimal). Then:
753 10 = 1361 8

14.

753 10 = 2F1 16
The method of converting a decimal number to base 2, or 8, or 16 can be
extended to any arbitrary base. Suppose you want to convert a decimal
number n into an equivalent number in base b , where b is between 2 and
36 . You then divide the decimal number n by b , as in the algorithm for
converting decimal to binary.
Note that the digits in, say, base 20, are 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , A , B , C , D ,
E , F , G , H , I , and J .
Write a program that uses a recursive method to convert a number in decimal
to a given base b ,where b is between 2 and 36 . Your program should
prompt the user to enter the number in decimal and in the desired base.

1
3