Sometimes, the best way to solve a problem is by solving a smaller version of the exact same problem first Recursion is a technique that solves a problem by solving a smaller problem of the same type.—Recursion is a problem-solving approach that can be used to generate simple solutions to certain kinds of problems that would be difficult to solve in other ways. —Recursion splits a problem into one or more simpler versions of itself.

When you use this technique in a program, you end up with functions that are called “recursive functions”.

int f(int x)
 int y;

    return 1;
 else {
    y = 2 * f(x-1);
    return y+1;

What is —Recursive algorithm?

Algorithm that finds the solution to a given problem by reducing the problem to smaller versions of itself. Has one or more base cases, Implemented using recursive functions. A recursive function is a function that calls itself.

Base Case: Case in recursive definition in which the solution is obtained directly is called Base case. It stops the recursion.

—General case: Case in recursive definition in which a smaller version of itself is called. Must eventually be reduced to a base case.

—There are many problems whose solution can be defined recursively. For example, factorial can be achieved through recursion.

Iterative Implementation of Factorial

int Factorial(int n)
 int fact = 1;

 for(int count = 2; count <= n; count++)
   fact = fact * count;

 return fact;

Recursive Implementation of Factorial

int Factorial(int n)
 if (n==0)  // base case
   return 1;
   return n * Factorial(n-1);

Recursion or Iteration? Which way to go!

—Iterative control structures: uses looping to repeat a set of statements. —In iteration, a loop repetition condition determines whether to repeat the loop body or exit from the loop. —In recursion, the condition usually tests for a base case.
—Tradeoffs between two options
  • Sometimes recursive solution is easier
  • Recursive solution is often slower
  • —You can always write an iterative solution to a problem that is solvable by recursion.
  • —Recursive code may be simpler than an iterative algorithm and thus easier to write, read, and debug.
  • —Recursive solutions are often less efficient, in terms of both time and space, than iterative solutions.
  • —Recursion can simplify the solution of a problem, often resulting in shorter, more easily understood source code

How Recursion works?—

Recursive function has unlimited copies of itself. Every recursive call has its own code, own set of parameters, own set of local variables.

—What happens when a function gets called?
int a(int w)
 return w+w;

int b(int x)
 int z,y;
// other statements
 z = a(x) + y;

 return z;
—An activation record is stored into a stack (run-time stack)
  1. The computer has to stop executing function    b and starts executing function a
  2. Since it needs to come back to function b later, it needs to store everything about function b that is going to need (x, y, z, and the place to start executing upon return) stores values of parameters and local variables
  3. Then, x from b is copied to w from a
  4. Control is transferred to function a
  5. —After function a is executed, the activation record is popped out of the run-time stack.
  6. —All the old values of the parameters and variables in function b are restored and the return value of function a replaces a(x) in the assignment statement
—Except the fact that the calling and called functions have the same name, there is really no difference between recursive and non-recursive calls.

After completing recursive call

  • Control goes back to calling environment
  • Recursive call must execute completely before control goes back to previous call
  • Execution in previous call begins from point immediately following recursive call

How to find a Recursive solution?

Following steps could be helpful to design a Recursive Algorithm:

  1. —There must be at least one case (the base case), for a small value of ‘n’, that can be solved directly
  2. —A problem of a given size ‘n’ can be split into one or more smaller versions of the same problem (recursive case)
  3. —Devise a strategy to split the problem into smaller versions of itself while making progress toward the base case
  4. —Recognize the base case and provide a solution to it
  5. —Combine the solutions of the smaller problems in such a way as to solve the larger problem

How do I write a recursive function?

  • —Determine the base case(s): the one for which you know the answer
  • —Determine the general case(s): the one where the problem is expressed as a smaller version of itself
  • —Verify the algorithm: use the “Three-Question-Method” given below.
Three-Question Verification Method
  1. The Base-Case Question: Is there a non-recursive way out of the function, and does the routine work correctly for this “base” case?
  2. The Smaller-Caller Question: Does each recursive call to the function involve a smaller case of the original problem, leading inescapably to the base case?
  3. The General-Case Question: Assuming that the recursive call(s) work correctly, does the whole function work correctly?
Example: Factorial
4! = 4 * 3 * 2 * 1
n! = n * (n-1) * … * 1
4! = 4 * 3!
n! = n * (n-1)!
factorial(n) = n * factorial(n-1)     //recursive step
factorial(1) = 1      //base step

Recursive Factorial Function 

int fact(int num)
   if(num == 0)
      return 1;
      return num * fact(num – 1);

Example: Fibonacci sequence

0, 1, 1, 2, 3, 5, 8, 13, 21, ….

int scndLast = 0;
int prev = 1;
for (i = 2; i <= n; i--)
		current = scndLast + prev;
		scndLast = prev;
		prev = current;
cout << “nth number in Fibonacci sequence is: ” << current;

When to use recursion?

  • —If recursive and iterative algorithms are of similar efficiency, use Iteration
  • —If it is easier to conceptualize an algorithm using recursion, use Recursion. The reduction in efficiency does not outweigh the advantage of readable code that is easy to debug
  • —Recursion is very inefficient when values are recomputed
Tagged with: C/C++ languageClasses

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.