Recursion in C++
To understand what really C++ Recursion is, we need to define it in different ways as following:
The process of solving a problem by reducing it to smaller versions of itself is called recursion. Recursion is a very powerful way to solve certain problems for which the solution would otherwise be very complicated.
More on Recursion:
When you call a function inside same function, is called Recursion. In other words when a method call itself recursion occurs.
At first this may seem like a never ending loop, or like a dog chasing its tail. It can never catch it. So too it seems our function will never finish. This might be true is some cases, but in practice we can check to see if a certain condition is true and in that case exit (return from) our function. The case in which we end our recursion is called a base case.
A definition in which something is defined in terms of a smaller version of itself.
- Every recursive definition must have one (or more) base cases.
- The general case must eventually be reduced to a base case.
- The base case stops the recursion.
The concept of recursion in computer science works similarly. Here, we talk about recursive algorithms and recursive functions. An algorithm that finds the solution to a given problem by reducing the problem to smaller versions of itself is called a recursive algorithm. The recursive algorithm must have one or more base cases, and the general solution must eventually be reduced to a base case.
A function that calls itself is called a recursive function. That is, the body of the recursive function contains a statement that causes the same function to execute again before completing the current call. Recursive algorithms are implemented using recursive functions.
concentrate on c++ recursion example below which prints the factorial of a number;
int fact(int num)
if (num == 0)
return num * fact(num - 1);
cout << fact(4) << endl;
The output of the previous cout statement is: 24
In the image above, the down arrow represents the successive calls to the function fact, and the upward arrows represent the values returned to the caller, that is, the calling function.
Let us note the following from the preceding example, involving the factorial function.
- Logically, you can think of a recursive function as having an unlimited number of copies of itself.
- Every call to a recursive function—that is, every recursive call—has its own code and its own set of parameters and local variables.
- After completing a particular recursive call, control goes back to the calling environment, which is the previous call. The current (recursive) call must execute completely before control goes back to the previous call. The execution in the previous call begins from the point immediately following the recursive call.
There are some types of recursion like: Direct, Indirect and Infinite Recursion.
More articles on programming, here.