Recursion is a programming tool which provides a powerful yet simple way of approaching numerous problems. Recursive functions can be summarized as a process being performed where one of the step is to "repeat the process". This makes it similar to a loop because of its ability to repeat the same lines of a code.
In programming context, if a piece of code allows you to call a function inside that same function, then it can be labelled as a recursive call of the function. Recursion makes it simpler to express ideas where the result of the recursive call is important to complete a task.
Let us take a simple example of recursive programming involving computing factorials. Factorial of a non-negative integer n denoted as n! can be computed as the product of all positive integers less than or equal to n.
For example,
factorial (5) is the same as 5*4*3*2*1, and factorial (3) is 3*2*1.
A point to be noted is that the factorial of a number is equal to the product of the same number and the factorial of the number immediately below it.
For example,
factorial (5) is the same as 5 * factorial (4).
The Recursive function in the part of code requires a condition to make it understand when to stop. Since factorials of numbers less than 1 does not make any sense, we stop at the number 1 and return the factorial of 1 (which is 1). Therefore, the factorial function will be as follows:
int factorial(int k) { if(k == 1) { return 1; } else { return k * factorial(k - 1); } }
The stopping point as discussed previously is called the base case. A base case is the bottom point of a recursive function where the operation is able to return an answer directly without calling the recursive function again. It is mandatory for all the recursive programs to have at least one base case. Otherwise the condition of infinite loop i.e. the program would run forever or until it ran out of memory or stack space.
Iteration and Recursion are both key Computer Science concepts that are used in creating numerous algorithms and developing software products.
Read more about Iteration and Recursion here
Let us go through the following sequence of steps to achieve recursive programming.
PROGRAM: #include< iostream> using namespace std; int sumofnum(int k); int main() { int k; cout << "Enter a natural number:"; cin >> k; cout << "Sum of numbers = " << sumofnum(n); return 0; } Int sumofnum(int k) { if(k != 0) return k + sumofnum(k - 1); return 0; } OUTPUT: Enter a natural number: 10 Sum of numbers = 55
PROGRAM: #include < iostream> using namespace std; int cal_hcf(int k1, int k2); int main() { int k1, k2; cout << "Enter the value of two natural numbers: "; cin >> k1 >> k2; cout << "H.C.F of the entered numbers " << k1 << " & " << k2 << " is: " << cal_hcf(k1, k2); return 0; } int cal_hcf(int k1, int k2) { if (k2 != 0) return cal_hcf(k2, k1 % k2); else return k1; } OUTPUT: Enter the value of two natural numbers: 366 60 H.C.F of the entered numbers 366 and 60 is: 6
PROGRAM: class Cal_factorial { int factorial(int k) { int answer; if ( k ==1) return 1; answer = factorial (k-1) * k; return answer; } } class FactRecursion { public static void main (String args[]) { Cal_factorial f =new Cal_factorial(); System.out.println(“Using recursion Factorial of 3 is “ + f.factorial(3)); System.out.println(“Using recursion Factorial of 4 is “ + f.factorial(4)); System.out.println(“Using recursion Factorial of 5 is “ + f.factorial(5)); } } OUTPUT: Factorial of 3 is 6 Factorial of 4 is 24 Factorial of 5 is 120
PROGRAM: public class Recursion { static int k1=0,k2=1,k3=0; static void Fibo(int ct){ if(ct>0){ k3 = k1 + k2; k1 = k2; k2 = k3; System.out.print(" "+k3); Fibo(ct-1); } } public static void main(String[] args) { int ct=15; System.out.print(k1+" "+k2); Fibo(ct-2); } } OUTPUT: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
Assignment Writing Help
Engineering Assignment Services
Do My Assignment Help
Write My Essay Services