Amu_Ke_Fundye

Recursion

A function that calls itself directly or indirectly is called a recursive function. The recursive factorial function uses more memory than its non-recursive counter part. Recursive function requires stack support to save the recursive function calls.

• Recursion leads to compact
• It is simple
• It is easy to understand
• It is easy to prove correct

Example-1: Factorial Recursive Function


Example-2: GCD Recursive Function

Example-3: Fibonacci Sequence Recursive Function


Example-4: Power Recursive Function (x^y)

Example-5: Searching maximum value of an array with function call max(a, 0, n-1).

int mid, leftmax, rightmax;
int max (int a[], int low, int high)
{
if (low == high) return a[low];
else
{
mid = (low + high) / 2;
leftmax = max (a, low, mid);
rightmax = max (a, mid + 1, high);
if (leftmax > rightmax) return leftmax;
else return rightmax;
}
}

Example-6: Computing the sum of numbers from 1 to n

int sum (int n)
{
int s;
if (n == 0) return 0;
s = n + sum(n-1);
return s;
}

Regards 

Amrut Jagdish Gupta