Recursion is an ability of a program to call itself, either directly or indirectly. Its a programming technique that naturally implements the divide and conquers programming approach. It does the task of calling itself. To do this, it must reduce its size upon every call; else, the process will become infinite.

Type of Recursion

  • Direct Recursion
  • Indirect Recursion

Example: To compute factorial of a number

The above program works as follows,

fact(5) = {if(5= =1) is false thus return 5* fact (4)}

fact(4) = {if(4= =1) is false thus return 4* fact (3)}

fact(3) = {if(3= =1) is false thus return 3* fact (2)}

fact(2) = {if(2= =1) is false thus return 2* fact (1)}

fact(1) = {if(1= =1) is true thus return 1}

Example: The Fibonacci series