Table of Contents
Recursion in Data Structure
Recursion is a process by which a function calls itself repeatedly, until some specified condition has been satisfied. The process is used for repetitive computations in which each action is stated in terms of a previous result. Many iterative problems can be written in this form.
A function is said to be recursively defined if the function definition refers to itself. In order for the definition not to be circular, it must have the following two properties:
- There must be certain arguments, called base values, for which the function does not refer to itself.
- Each time the function does refer to itself, the argument of the function must be closer to a base value.
Examples:
Factorial Function:-
The product of the positive integers from 1 to n, is called “n factorial” and is usually denoted by n!
n! = 1.2..3………(n – 2) (n – 1) n Also, 0! = 1
So, 0! = 1, 1! = 1 2! = 1.2 = 2 3! = 1.2.3 = 6
4! = 1.2.3.4 = 24 5! = 1.2.3.4.5 = 120
and so on.
Also, 5! = 5.4! = 5.24 =120 and 4! = 4.3! = 4.6 = 24
So, we can say that n! = n. (n – 1)!
Now, factorial function can be defined as:
- If n = 0 then n! = 1
- If n > 0 then n. (n – 1)!
Algorithm: FACTORIAL (FACT, N)
This procedure calculates N! and returns the value in the variable FACT.
Step 1: If N = 0 then
FACT := 1 and
Return.
Step 2: Call FACTORIAL (FACT, N – 1)
Step 3: FACT := N * FACT
Step 4: Return.
Recursion Vs. Iteration:
Iteration | Recursion |
It is a process of executing a statement or a set of statements repeatedly, until some specified condition is specified. | When a function calls itself, it is called recursion. |
Iteration involves four steps: initialization, condition, execution and updation. | There must be an if statement inside the recursive function, specifying stopping condition. |
Any recursive problem can be solved iteratively. | Not all problems have recursive solution. |
Iterative counterpart of a problem is more efficient in terms of memory utilization and execution speed. | Recursion is generally a worse option to go for simple problems. |
Algorithm of Factorial using iteration:
FACTORIAL (FACT, N)
This procedure calculates N! and returns the value in the variable FACT.
Step 1: If N = 0 then
FACT := 1 and Return.
Step 2: FACT := 1
Step 3: Repeat for K = 1 to N
FACT := K * FACT
[ End of Loop ]
Step 4: Return.
Fibonacci sequence
The Fibonacci sequence (F0, F1, F2,…………. ) is as follows:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,…………..
That is, F0 = 0 and F1 = 1 and each succeeding term is the sum of the two preceding terms. A formal definition of this function follows:
- If n = 0 or n = 1, then Fn = n
- If n > 1 then Fn = Fn – 2 + Fn – 1
Algorithm: FIBONACCI (FIB, N)
This procedure calculates Fn and returns the value in the first parameter FIB.
Step 1: If N = 0 or N = 1, then
FIB := N and return.
Step 2: Call FIBONACCI (FIBA, N – 2)
Step 3: Call FIBONACCI (FIBB, N – 1)
Step 4: FIB := FIBA + FIBB
Step 5: Return.
You May Like to Browers More
