Understanding Recursive Functions in Programming
Recursive functions in programming are powerful tools that can be used to solve complex problems by breaking them down into smaller, more manageable sub-problems. This content explores how recursive methods can be implemented using examples like the pool rack and division functions, showcasing the concept with detailed explanations and sample code snippets.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
The pool rack example could be implemented using a for loop. It is also possible to write recursive methods that accomplish things that you might do with a while loop.
A recursive definition is given below for finding how many times the constant value 2 will go evenly into another number. The value 1 which is added in the recursive case counts how many times recursion occurs. This count gives the result of the division. Notice that in the recursive case n is no longer decremented by 1. It is decremented by 2.
The test for the base case is an inequality rather than an equality since the values that n takes on vary depending on whether it is initially odd or even. Recursive case: n >= 2 f(n) = 1 + f(n 2) Base case: n < 2 f(n) = 0
Here is a sample implementation. The recursive method recursiveDivisionByTwo() is typed int and takes an int parameter named dividend. public static int recursiveDivisionByTwo(int dividend) { if(dividend < 2) return 0; else return 1 + recursiveDivisionByTwo(dividend 2); }
Building on this example, it is possible to write a recursive definition for the general division function. This is shown on the next slide. The function has two parameters. Adding 1 in the recursive case again counts how many times the recursion occurs. In this definition the first parameter for the recursive case is dividend divisor. The amount decremented each time is always the same, but divisor can be any (positive integer) value. The second parameter is the divisor, which is passed down unchanged through all of the calls.
Recursive case: dividend >= divisor f(dividend, divisor) = 1 + f(dividend divisor, divisor) Base case: dividend < divisor f(dividend, divisor) = 0
Here is a complete driver program and an implementation of this function. As usual, this is not a general implementation, but it works for appropriate input values and illustrates the key points. Notice that a variable retVal is used in the implementation.
import java.util.Scanner; public class GenRecDivProg { public static void main(String[] args) { Scanner in = new Scanner(System.in); int retVal; int dividend, divisor; System.out.print("Enter the dividend: "); dividend = in.nextInt(); System.out.print("Enter the divisor: "); divisor = in.nextInt(); retVal = GenRecDivClass.genRecDiv(dividend, divisor); System.out.println(retVal); } }
public class GenRecDivClass { public static int genRecDiv(int dividend, int divisor) { int retVal = 0; if(dividend < divisor) return retVal; else { retVal = 1 + genRecDiv(dividend - divisor, divisor); return retVal; } } }
Just as division can be defined by repeated subtraction, finding a logarithm can be defined by repeated division. For a given number to find the log of, which will be represented by the variable name toFindLogOf, and a given base, a simple recursive definition of the logarithm function would look like this: Recursive case: toFindLogOf >= base f(toFindLogOf, base) = 1 + f(toFindLogOf / base, base) Base case: toFindLogOf < base f(toFindLogOf, base) = 0
The following example contains two static methods, both of which find a simple logarithm by doing repeated division. One does so with looping and the other with recursion. For positive input consisting of a given double toFindLogOf and a given integer base, the code gives as output the largest integer value less than or equal to the logarithm for that number and base.
import java.util.Scanner; public class TestRecAndLoop { public static void main(String[] args) { Scanner in = new Scanner(System.in); double toFindLogOf; int base; double answer; System.out.println("What number would you like to find the log of?"); toFindLogOf = in.nextDouble(); System.out.println("What should the base of the logarithm be?"); base = in.nextInt(); answer = RecursionAndLooping.myLogLooping(toFindLogOf, base); System.out.println("The looping answer is: " + answer); answer = RecursionAndLooping.myLogRec(toFindLogOf, base); System.out.println("The recursive answer is: " + answer); } }
public class RecursionAndLooping { public static int myLogLooping(double toFindLogOf, int base) { int retVal = 0; while(toFindLogOf >= base) { toFindLogOf = toFindLogOf / base; retVal++; } return retVal; } public static int myLogRec(double toFindLogOf, int base) { int retVal = 0; if(toFindLogOf < base) return retVal; else { toFindLogOf = toFindLogOf / base; retVal = 1 + myLogRec(toFindLogOf, base); return retVal; } } }
Note that the following version of the recursive method is shorter, but it might also be a little bit harder to understand. public static int myLogRec(double toFindLogOf, int base) { int retVal = 0; if(toFindLogOf > base) { toFindLogOf = toFindLogOf / base; retVal = 1 + myLogRec(toFindLogOf, base); } return retVal; }
