Recursion

What is Recursion?
The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Using recursive algorithm, certain problems can be solved quite easily

What is base condition in recursion?
In the recursive program, the solution to the base case is provided and the solution of the bigger problem is expressed in terms of smaller problems.

int fact(int n)
{
    if (n < = 1) // base case
        return 1;
    else    
        return n*fact(n-1);    
}

In the above example, base case for n < = 1 is defined and larger value of number can be solved by converting to smaller one till base case is reached.

How a particular problem is solved using recursion?
The idea is to represent a problem in terms of one or more smaller problems, and add one or more base conditions that stop the recursion. For example, we compute factorial n if we know factorial of (n-1). The base case for factorial would be n = 0. We return 1 when n = 0.

Why Recursion Works

In a recursive algorithm, the computer “remembers” every previous state of the problem. This information is “held” by the computer on the “activation stack” (i.e., inside of each functions workspace).

Every function has its own workspace PER CALL of the function.

Simple Example: Add three numbers

Adding three numbers is equivalent to adding the first two numbers, and then adding these two numbers again.

function result = add_numbers(a, b, c) 
 
          if      ( nargin() == 2 ) 
            result = a + b; 
          else if ( nargin() == 3 ) 
            result = add_numbers(a+b, c); 
          else 
            error('oops'); 
          end 
           
        end