Recursion in C++
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 problemsolving 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; if(x==0) return 1; else { y = 2 * f(x1); 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.
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; else return n * Factorial(n1); }
Recursion or Iteration? Which way to go!
 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.
int a(int w) { return w+w; } int b(int x) { int z,y; // other statements z = a(x) + y; return z; }
 The computer has to stop executing function b and starts executing function a
 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
 Then, x from b is copied to w from a
 Control is transferred to function a
 After function a is executed, the activation record is popped out of the runtime stack.

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
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:
 There must be at least one case (the base case), for a small value of ‘n’, that can be solved directly
 A problem of a given size ‘n’ can be split into one or more smaller versions of the same problem (recursive case)
 Devise a strategy to split the problem into smaller versions of itself while making progress toward the base case
 Recognize the base case and provide a solution to it
 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 “ThreeQuestionMethod” given below.
 The BaseCase Question: Is there a nonrecursive way out of the function, and does the routine work correctly for this “base” case?
 The SmallerCaller Question: Does each recursive call to the function involve a smaller case of the original problem, leading inescapably to the base case?
 The GeneralCase Question: Assuming that the recursive call(s) work correctly, does the whole function work correctly?
4! = 4 * 3 * 2 * 1 n! = n * (n1) * … * 1 4! = 4 * 3! n! = n * (n1)! factorial(n) = n * factorial(n1) //recursive step factorial(1) = 1 //base step
Recursive Factorial Function
int fact(int num) { if(num == 0) return 1; else 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
Related Posts
 This Pointer, Static Members and destructors in C++
 Introduction to Recursion in C++
 Exception Handling in C++
 Inheritance in C++
 More on Destructors and Static Data Members in C++
 Polymorphism in C++
 C++ Tutorial for Intermediate Programmer
 Introduction to Classes and Objects in C++
 Implementing a Queue as a Linked List Data Structure in C++
 UIKit Views and Animation – iPhone Development
 Merge Sort with Graphical explanation
 Quick Sort Algorithm with Graphical Explanation
Popular Posts (last 30 days)
 Attendance Management Sys… 1203 view(s)
 Implementing Stack Data S… 596 view(s)
 Graph Implementation in C… 594 view(s)
 Applications of Stack in … 536 view(s)
 Circular Linked Lists 526 view(s)
 Simple Currency Converter… 444 view(s)
 GRASP Design Patterns 330 view(s)
 Advanced Data Structures … 268 view(s)
 C++ Tutorial for Intermed… 260 view(s)
 Sockets and Network Progr… 187 view(s)
Related Links
Tags
Android CSharp C/C++ language Classes Data structures Design Pattern Eclipse Game Development Graphics Design Books HTML iPhone JAVA JAVA GUI MIPS Assembly Mobile Programming Books Object Oriented PDF PHP Programming Programming Books Programming Languages Books Python RaphaelJS REST Source Code Threads Tutorial Web Development Books