Recursive Functions - An Introduction
An essential feature of any programming language is functions. A set of instructions that performs logical operations, which can be very complex and numerous in number, can be grouped as functions (or procedures). Functions may call themselves or other functions, and the called functions may call the calling function. This process is called recursion, and such functions are called recursive functions. A recursive function makes the program compact and readable.
Programmers follow the best practices for writing readable and error-free code. Functions are the most helpful tool that accomplishes this. You call a function using its name and parameters when you have a function. It will be executed and then return its results to the place where it was called in the calling function. Recursion is when a function calls itself, either directly or indirectly. With recursive functions, there is clarity your program. Programs with recursive functions provide many benefits such as being, readable and concise. Recursion has various benefits such as making it easier to solve complex problems, minimizing confusion with your program, and more.
Let us consider an example of computing the factorial of a number. Factorial is a mathematical term. The factorial of a number, say n, is equal to the product of all the integers from 1 to n. The factorial of n is denoted as
Let us consider an example of computing the factorial of a number. Factorial is a mathematical term. The factorial of a number, say n, is equal to the product of all the integers from 1 to n. The factorial of n is denoted as
n! = 1 * 2 * 3 * … * n or n! = n * n − 1 * … * 1 (a)
For example, 10! = 1 *2 *3 * 4 * 5 * 6 * 7 * 8 * 9 * 10. The simplest program to calculate the factorial of a number is by using a loop with a product variable.
Algorithm (a). states the iterative process of computing the factorial of n as 10! = 10 * 9 * 8 *... * 1.
ALGORITHM (a)
An iterative version of an algorithm to compute the factorial of a number 1. start 2. Let n be the number whose factorial is to be computed and let Factorial = 1 3. while(n > 1) do begin Factorial = Factorial * n n = n – 1 end 4. stop The iterative process of computing the factorial of n in Algorithm (a). can also be written as in Algorithm (b).
ALGORITHM (b)
An iterative version of the algorithm to compute the factorial of a number 1. start 2. Let n be the number whose factorial is to be computed and let Factorial = 1 3. for I = 1 to n do // I can also be initialized to 2 begin Factorial = Factorial * I End 4. stop
Algorithms (a) and (b) are iterative algorithms for computing the factorial of n. It is possible to give a recursive definition for factorial too. The mathematical function defined in Eq. (a) for factorial of n can also be defined recursively as
n! = n * (n − 1)!, where 1! = 1 (b)
This recursive definition of factorial has two steps, as follows:
1. If n = 1, then factorial of n = 1
2. Otherwise, the factorial of n = n * factorial of (n − 1)
Program Code (a) demonstrates the recursive code for Algorithm (a).
The Factorial() function is an example of a recursive function. In the second return statement, the function calls itself. The important thing to remember when creat- ing a recursive function is to give an end condition. In Program Code (a), the recursion stops when n becomes 1. In each call of the function, the value of n keeps decreasing. However, when the value reaches 1, the function ends. On the other hand, this function will run infinitely if the initial value of n is less than 1, which means that the function is not perfect. Therefore, the condition n = 1 should be changed to n ≤ 1. Let us rewrite the Factorial() function as in Program Code (b).
Program Code (b) takes advantage of the fact that the factorial of any integer n can be defined recursively as the product of n and the factorial of n − 1. For example, 5! = 5 ¥ 4!