Can someone help me?

[TiKe]

Can someone explain recursion to me?
I just can't understand it

[Repeater]

Recursion is calling a function from within that same function.

Imagine a function exists. Let's call it someFunction()

Here it is:

void someFunction()
{

}

As you can see, it does nothing. If it calls itself, that is recursion.

void someFunction()
{
  someFunction();
}

This particular recursive function isn't very useful. It will just call itself forever (or at least until the stack runs out of space and it's impossible to call any more functions), but it's a simple recursive function.

[arf]

There is an article about recursion functions:
http://www.cplusplus.com/articles/D2N36Up4/

[keskiverto]

How much is A + B + C + D + E?
You have to do some addition to find the answer.

Lets write that differently: sum( A, B, C, D, E )
Isn't that, by definition, equal to sum( A, B, C, D ) + E?

In other words, we can solve a larger problem sum( A, B, C, D, E )
by solving first a smaller problem X = sum( A, B, C, D ) and then do addition X + E.

How do we solve sum( A, B, C, D )?
We can solve Y = sum( A, B, C ) first, and then do Y + D.

The "smallest subproblem" is trivial to solve: sum(A) == A


Put other way:
You are a boss in company. Company got a problem.
You call your minions and let them have it.

Your minions are (smaller) bosses too. They do exactly what you did:
Call their minions and let them have it.

Everybody in the chain of command does effectively the same routine (but for different audience). Everybody in the company gets the message, even though you did not go to talk to everyone yourself.

[The Brahmnic Boy]

So we can compute Mathematical series using this?

Like summation of Fibonacci sequence or Factorials?

Can we use the Riemann formula for number of primes under a threshold?

[Ganado]

Recursion is a type of iteration, so yes, you can. Though, I would say most things are better suited to do with iteration (think for/while loops) than recursion, including something like the prime-counting function. https://en.wikipedia.org/wiki/Prime-counting_function
Whenever you see a summation sigma in math, think "for loop" in most cases.

Fibonacci is another example of a sequence that's actually really inefficient to do by the naive recursive method (run-time becomes exponential). I would rather do Fibonacci with normal iteration.

But even if the logic/complexity is the same, I would still prefer iteration because the stack is comparatively limited in the amount of recursive calls it can handle.

[tpb]

#include <iostream>
using std::cout;

void iteration(int n) {     // count down from n to 1
    for ( ; n > 0; --n)
        cout << n << '\n';
}

void recursion(int n) {     // count down from n to 1
    if (n <= 0) return;
    cout << n << '\n';
    recursion(n - 1);
}

int main() {
    iteration(5);
    cout << '\n';
    recursion(5);
}

Objects can have recursive definitions. E.g., "A binary tree is either empty or consists of a root node whose left and right branches are binary trees." The definition of binary tree references "binary tree" inside it. The reason this is okay (doesn't create a necessarily infinite structure) is that there is always at least one base case that let's you stop the recursion. In this definition it's the "empty" tree.

An object with a recursive definition is often best processed using a recursive function. Here's an example of a binary tree.

#include <iostream>
using std::cout;

struct Tree {
    int n;
    Tree *left, *right;
    Tree(int n) : n{n}, left{}, right{} {}
};

void add(Tree*& t, int n) {
    if (!t)
        t = new Tree(n);
    else if (n < t->n)
        add(t->left, n);
    else
        add(t->right, n);
}

void prn(const Tree* t) {
    if (!t) return;
    prn(t->left);
    cout << t->n << '\n';
    prn(t->right);
}

int main() {
    Tree *t = nullptr;
    for(auto x: {5, 8, 3, 7, 4, 9, 1, 6, 0, 2})
        add(t, x);
    prn(t);
}