Recursion
Recursion is when we repeat a task 'A' some number of times to accomplish some task 'B.
Recursion becomes an important tool when a bigger problem 'B' can be solved by repetitive solving a smaller problem 'A'
Some definitions are naturally recursive whereas sometimes we have to figure out the problem and define a recursive relation
Factorial of a number n is a classic example of recursion.
fact(n) = 1 * 2 * 3 * ..... * n , i.e., product of first n natural numbers
we can define recursion as fact(n) = n * fact(n-1)
base condition is required so as to stop the recursion at some stage
we define fact(1) = 1 as base condition
infact in stringent mathematical terms, fact(0) is defined as 1, which is the base condition owing to the foundation principles of permutation and combinations
We can write it in function notation as on the right
There's a recursive condition and a base condition
This is a pseudo code
Below are illustrations which show how stack winds and unwinds during recursion
Activation records are pushed during winding and popped during unwinding
Recursion can be classified into different types:
This type is called self recursion since the function is calling itself
The core concept of recursion remains the same