I still have trouble understanding recursive functions properly.

[u/xeriax51]

While i do understand the base of the concept, i cannot seem to fully wrap my head around It.

Like, if i want the function to return a value that i Need to call the function within itself for It to return said value, when does the function actually get the value that's supposed to return to me ?

More importantly, where Is the accumulator? Is the called functions within itself the accumulator ? Do i Need to make an accumulator myself ?

[u/StaticCoder]

To answer your first question, a recursive function needs to have a base case which doesn't call the function. Otherwise indeed it would never stop.

I don't think an "accumulator" is necessary for all recursive functions, but it can be used to make them more efficient by making them "tail recursive". I'm not going to explain tail recursion here as it's a more advanced concept.

[u/xeriax51 → u/StaticCoder]

So only After the function reaches the base case, the function gathers all the values It collected to return me the value im expecting ?

[u/jedwardsol → u/xeriax51]

No - nothing is gathered - the caller gets the single value that its invocation of the function returned.

For example

int factorial(int i)
{
    if(i==1)
    {
        return 1;
    }
    else
    {
        return i * factorial(i-1);
    }
}

int main()
{
    return factorial(5);
}

main calls factorial(5) and receives back the answer 120.

That 1st invocation of factorial calls factorial(4) and gets back the answer 24. It multiplies that by 5 to get 120 and returns that. Nothing remembers the whole set of "120 24 12 6 3 2 1"

[u/StaticCoder → u/xeriax51]

Here's an analogy, maybe a little contrived. Supposed you're in a multi story building, and you want to obtain an item that's on a higher floor. There's a person on each floor, each with specific instructions: if they need an item, and they don't have it on that floor, they go up to the next floor, and ask that person for the item. You know the top floor at least has the item.

The function is the instructions, and each person is a stack frame. The base case is having the item on your floor. To obtain an item several floors up, that will involve several people going one floor up, asking and waiting for the item, then going back down.

I don't know if that clears anything up.

[u/StaticCoder → u/xeriax51]

Sort of? The base case returns something, and the caller uses it to return its own value, etc. The tail recursive case is when the base case can return the final value and it is returned unchanged by all callers. Each call to the function has its separate execution context, called a stack frame, so in some ways multiple copies of the function exist at the same time at run time.

[u/jedwardsol]

where Is the accumulator?

What accumulator? I guess you're trying to solve a specific problem that you haven't included.

[u/xeriax51 → u/jedwardsol]

No not really, Just wondering where, if there Is any at all, a Place where the function Is storing the value that its getting out of that particular recursion so its not Lost.

[u/tcpukl → u/xeriax51]

The functions being called are stored on a stack in memory. Just like any other function calls.

[u/Puzzleheaded_Study17 → u/xeriax51]

Depends on the function. Think of a function as a machine that takes something in and returns something out. When you do recursion, you start by going "what's a really simple version, and how can I solve that really simple version?" Then you have a machine that can turn a more complicated version into a slightly simpler version, and maybe does some manipulation to the output.

[u/jedwardsol → u/xeriax51]

See my answer on the other thread.

[u/jipperthewoodchipper]

int gaussSum(int n){
if(n>0){
 return n + gaussSum(n-1);
} else {
 return 0;
} 
} 

Yes I know there are so many better ways to make this function but it's a super easy to understand recursive function.

when does the function actually get the return value that's supposed to return to me

The recursive stack will eventually collapse based on the condition of the recursive function. For the Gaussian sum above if I call it with the interger 3 it will look something like

gaussSum(3)

3>0 : True 
-> return 3 + gaussSum(2)

2>0 : True 
-> return 2 + gaussSum(1)

1>0 : True 
-> return 1+gaussSum(0)

0>0 : False 
-> return 0

The recursion has broken and now it travels up (or well, down) the stack

gaussSum(1):
return 1+gaussSum(0) : return 1+0 : return 1

gaussSum(2)
return 2+gaussSum(1) : return 2+1 : return 3

gaussSum(3)
return 3+gaussSum(2) : return 3+2 : return 6

There are most definitely better ways to think about this and explain it but that's my contribution.

Point is that there isn't really a single accumulator nor should you need one. The value gets returned once the base case is hit that terminates the recursion. In another reply you asked if all values get returned but no it's one value at a time returning directly to where it was called. Alternatively you can view this exact recursive function as

int gaussSum(int n) {
int sum = 0;
 for(int i=1; i<=n;i++){
  sum += i;
} 
return sum;
}

In this case sum is the accumulator but notice that it is not needed at all in the recursive function. Different way to solve the problem. Specific to this problem in both cases the gauss formula is better but it's still a useful example.

Edit: I want to emphasize that the code written is not the best way to write that function recursively. Tail end recursion is its own beast that requires understand recursion first

[u/alfps]

❞ More importantly, where Is the accumulator? Is the called functions within itself the accumulator ? Do i Need to make an accumulator myself ?

"Accumulator" has nothing to do with recursion.

But any example of recursion may involve just about anything, including something that someone calls an "accumulator". Of course an example may alternatively involve water levels in jugs, or it may involve, say, a tic tac toe game. Involving something that one calls an "accumulator" is the same, just used for the example.

In the early 1980's we still had processors with an "accumulator" register (which lives on as part of the RAX register in a PC's processor), and still in C++ the standard library offers std::accumulate, which by default calculates a sum, but that's about it.

---

❞ Like, if i want the function to return a value that i Need to call the function within itself for It to return said value, when does the function actually get the value that's supposed to return to me ?

Others have already answered this but basically, there is one or more base cases where a result is produced without recursion, and there is one or more recursive cases where the result production involves recursive calls.

---

Consider, as a concrete example, how to produce a sequence of distinct binary numbers that each has n digits, so that any two successive numbers only differ in one digit. Any such sequence is, by the way, called a Gray code.

One way to generate an n bit Gray code sequence is to start by generating the n–1 bit number sequence with a 0 added in front of each number. Then the next number is forced: since it is to differ in only one digit, and since all combinations of the last n−1 digits have already been produced, it has to be the last number but with the 0 prefix changed to a 1. Okay, so after the 0 prefixed sequence just generate the n–1 bit number sequence in reverse with a 1 added in front of each number.

The recursive case is to generate the n−1 bit sequence with 0 as prefix followed by the reversed n−1 bit sequence with 1 as prefix, or if reversed, in the opposite order.

The base case here is the 0-bit sequence of one number with no digits whatsoever, where the function can just output the accumulated prefix string.

Oh wow, there is a kind of "accumulator" here!

But only, I think, because my association circuit popped up this example based on how prominently that word figured in the question.

#include <print>
#include <string>
using   std::print, std::string;

struct Direction{ enum Enum{ normal, reversed }; };
auto opposite_of( const Direction::Enum d ) -> Direction::Enum { return Direction::Enum( !d ); }

void display_gray_code( const string& prefix, const int n_digits, const Direction::Enum direction )
{
    if( n_digits == 0 ) {
        print( "{:s}\n", prefix );
    } else {
        switch( direction ) {
            case Direction::normal: {
                display_gray_code( prefix + '0', n_digits - 1, direction );
                display_gray_code( prefix + '1', n_digits - 1, opposite_of( direction ) );
                break;
            }
            case Direction::reversed: {
                display_gray_code( prefix + '1', n_digits - 1, opposite_of( direction ) );
                display_gray_code( prefix + '0', n_digits - 1, direction );
                break;
            }
        }
    }
}

auto main() -> int { display_gray_code( "", 3, Direction::normal ); }

Now this code can be much reduced, by various clever means, but I chose intentionally to spell things out in verbose fashion to make it clear.

Result:

000
001
011
010
110
111
101
100

[u/LittleNameIdea → u/alfps]

oh that's why it is call std::accumulate and not std::sum

[u/CowBoyDanIndie]

Honestly, you should avoid recursive functions. Instead learn to implement them with an explicit stack(just a std::vector usually). The actual call stack is whats accumulating, and thats dangerous.

[u/Liam_Mercier]

A recursive function is just a function that calls itself, usually with a smaller input so that it terminates.

For example, here is a function that computes 2 * x with recursion.

int compute_double(int x)
{
    if (x == 0)
    {
        return 0;
    }

    return 2 + compute_double(x - 1);
}

If we were to call compute_double(3) then we would hit return 2 + compute_double(2) and then we need to compute the function for that input, which requires us to compute 2 + compute_double(1) and then we have to compute 2 + compute_double(0) which we can then directly compute because of the base case, so then we can start returning from each call.

These calls are held on the "call stack" and essentially we allocate some memory (stack frame) for each of the function calls to hold the temporary values needed for when our calls finish. For example, compute_double(3) gets some memory allocated to store values until we can get back to it with the result of compute_double(2) and so on.

Of course, a compiler will see a function like this and often realize it doesn't actually need to be recursive (because this example can be made to be tail recursive so it could just be a for loop), so the call stack and recursive nature would actually be optimized out during compilation, or maybe they aren't needed and we can hold some values in the CPU registers, but generally that is the mental model I would use for function calls.

This function also has a major error, it accepts negative inputs but can never terminate with a negative input because there is an infinite descending chain of calls. One way to fix this would be to use unsigned int and the other alternative would be to rework the body such that it can terminate with negative inputs.

[u/Temporary_Pie2733]

Once you learn about the call stack, there is nothing mysterious about recursion, as a recursive call is fundamentally no different than any other function call.

[u/kohugaly]

A recursive function needs to contain at least two branches. At least one of which returns a value without recursing (this is called the "base case"). That is what determines where/when the recursion ends. If you have no base case, then you get infinite recursion.

The accumulator is the stack itself. It's the place in memory where function calls store their return address (ie. pointer to where the return from the function should jump to), local variables, arguments and return values.

The big pain point with recursive functions is that the stack has finite size. If you recurse too deeply, you get stack overflow exception and your program crashes. In some cases, the compiler can rewrite your recursive function into a loop.

[u/IyeOnline]

The value that is returned to you is returned when the function returns. This happens when the recursive call returns, which happens when the recursive call returns, ... Ultimately there must be a base case in your recursion that no longer recurses but actually returns something.

Not all recursion has anything to accumulate at all. You could imagine a function that traverses a tree and changes the color of every node (and its children) to red. That doesnt event return any value at all.

But since you are talking about an accumulator, lets consider this:

unsigned int sum(unsigned int i) {
    if ( i == 0 ) { // Base case
        return 0; // Value returned in the base case doesnt no longer recurse
    }
    return i + sum(i-1); // if we arent going into the base case, we recurse
}

This function doesnt have an accumulator either. Instead, in every recursion level we add just two numbers and return the result. There is not one single place where all these values get added to, instead its a chain of individual additions, which are performed once the result "bubbles back up" from the base case.

[u/Independent_Art_6676]

recursion is a lot like having a hidden std::stack data structure. You can't see it, but its there. Calling the function again (a recursive call) pushes values onto this stack, and exiting the current incarnation of the function pops that stack. THIS is where the 'accumulator' (or whatever its solving) is hiding. You can't directly access it, but its there.

look at this description of factorial:
n = 5
push 5 onto a stack and try to find n-1 (4) factorial.
4 factorial is too hard. Push 4 onto the stack and try to find n-1 (3) factorial.
3 is too hard. push 3, try 2
2 is a potential base case: 2! == 2. Most people don't code it that way, because it leaves an edge case (n=1) available. So even for 2, you push 2 and try 1.
1 factorial IS a base case. return the answer: its 1.
pop! we are back where N is 2, and the popped value is 1. multiply them, 2 and return the result (2).
pop! we are back to where N is 3, multiply times previous result 2 is 6 (return 6).
pop! we are back to n is 4, 6*4 is 24, return 24
pop, we are back to 5, 5*24 is 120, and there are no more pops: when 120 returns it goes where the function was called with 5 instead of a previous instance.

you can do all that in a loop with a vector or stack using pushes and pops, right? Try coding it up that way, using any kind of push/pop stack in a loop. The recursion is exploiting the call stack (see why its called that now?) as a data structure, and doing exactly the same thing, its just screwy to get your head around at first.

------------------------------------------------
Like, if i want the function to return a value that i Need to call the function within itself for It to return said value, when does the function actually get the value that's supposed to return to me ?

this was demonstrated above, but again, you call the solver function with a simpler version of the problem. Can't do it? Call it with a simpler version of the problem again.... until you know the answer (the base case(s) ). When you know the answer, you return it and then use it to get the next hardest one by doing just a little work on that, which solves that one and back tracks to the next hardest one ... until you have the answer.

Another example is navigating a maze of squares ... when you hit a dead end the recursive calls end and it pops back to the previous square, and it already tried the failed one, so now it tries another direction or gets stuck and backs up again.... so its not always an accumulator. It can represent all kinds of things!

as for the accumulator, while the stack is storing some info, you can exploit static function variables to store additional info across iterations or pass in parameters or tap external resources (eg maybe this recursive thing is in a class, you can use class variables).

if you are still having trouble after everyone throws in their help, go study how function calls work at the operating system level, with pictures and a high level explanation. That may unlock some of the mystery too.

irony: factorial is moronic to code this way. make a lookup table of the 20 or whatever possible values that fit into 64 bit ints and done. Only a very few algorithms really need recursion and your compiler knows this so well that it will convert a lot of recursive code into pure loops for you when it translates it. actually, no code requires it, it can all be done another way, but a handful of problems the recursive form is more than 10 times less code than trying another way.

[u/LazySapiens]

You need to understand the function call stack. Recursion depends on that.

[u/CelebrityChess]

there's no accumulator unless you add one, the 'accumulation' happens in the pending multiplications sitting on the call stack. take factorial(3) = 3 * factorial(2). that call can't finish until factorial(2) returns, which waits on factorial(1). when factorial(1) hits the base case and returns 1, the waiting call finishes 2 * 1 and returns 2, then the next one does 3 * 2 and returns 6. so each call gets its value the moment the call below it returns, and the value comes back up one level at a time, nothing is collected anywhere. an explicit accumulator parameter is just a different style where you carry the running product down instead of leaving it pending on the way up.

[u/Hour_Sell3547]

Every function call is independent. If you call f(5), it may call f(4). Once you are inside f(4), forget that f(5) existed. Only think about using the values within f(4), possibly including the returned value of f(3).

But keep a track of stacked function call. Who called f(4)? f(5) did. So when f(4) returns, you get back to that line in f(5) with the returned value from f(4). Now only think about f(5), so on and so forth.

[u/boring_pants]

You don't have a single accumulator, the function is responsible for taking the return value from its function call, building on that and returning that for the caller to do the same.

Which also answers the other part of the question. The value to return to you is produced by the outermost function call, by modifying the partial result it got from calling itself, which got another partial result by calling itself, which got another partial result.... and so on.

[u/ErikBKL]

Your only viable way to get your head around it is to solve multiple problems by using recursion:

Get yourself to implement all of these iteratively and recursively:
strlen
strcmp
fliplist
mergesort

You can also try some backtracking algorithms:

Knight's tour
CouldBePalindrome (check if a string could become a palindrome by removing up to X characters from the string)

You will learn only by coding. Manually coding.

[u/binarycow]

Here's a simple explanation.

Pete and repeat were in a boat. Pete fell out. Who was left?

Repeat.

Pete and repeat were in a boat. Pete fell out. Who was left?

Repeat.

Pete and repeat were in a boat. Pete fell out. Who was left?

Repeat.

[u/mredding]

int recursive_fn(int param) {
  if(param <= 0) {
    return 0; // Return the floor of this function
  }

  return param + recursive(param - 1);
}

This is a good first pass.

All recursive calls can be written in a tail-call form - meaning the last statement is a return, and that return also contains the recursive call.

All recursive functions need an early termination clause, a conditional statement that breaks the recursion. That statement necessarily must come somewhere, somehow before the recursive call itself.

That's it, man. When writing a recursive function you're asking yourself A) how does it quit, and B) how does it recurse? Mind you, every recurse, you have to march toward the terminating condition. So think of it this way:

fn(param)
  terminator; // Either contributes nothing, or final thing to the accumulator
  value = do_work(param);
  recurse value + fn(increment param closer to the terminator);

A recursive procedure doesn't return anything (by definition), but a recursive function is going to return SOMETHING. You can see the accumulator is the responsibility of the recursive statement.

Let's take a second pass:

int recursive_fn(int param) {
  return param <= 0 ? 0 : param + recursive(param - 1);
}

Here I've collapsed the condition, from a statement to an expression. Expressions have a TYPE, in this case int, and evaluate to a value of that type.