Hello Everyone

I am trying understand the flow of recursive functions in the context of C language,

I've attempted to create a flowchart to visualize the execution of a recursive function, but I'm uncertain about certain aspects and would greatly appreciate your expertise to clarify them.

 

The fowchart you show cannot return anything but one, maybe you should correct it first.

 

The fowchart you show cannot return anything but one, maybe you should correct it first.

Just a quick note to clarify that the factorial of zero or one always equals one, Thats reason I am returning one in these cases

 

Look at your flowchart again. Where does it return anything other than one?

 

Look at your flowchart again. Where does it return anything other than one?

I believe the function should be called four times, with each call returning a value. It would look something like this:

fun(4)
fun(3)
fun(2)
fun(1)

So, if the function executes four times, each call should return a value. Please Let me know further clarification on how and when the function returns values?

 

Your flow chart does not capture the essence of the factorial function, which involves multiplying the current value of n by the factorial of (n-1).

Flow charts are not good representations for the internals of recursive algorithms because they do not capture that each invocation of the function has its own set of variables that do not interact with the variables in other invocations.

You are NOT calling the SAME function, you are calling a new COPY of the function (conceptually).

There is NOTHING special about recursion. Imagine the following:

int fact(int n)
{
   if (n <= 1)
      return 1;
   return n * fact2(n - 1);
}

You have one function, fact(), that calls another function, fact2(). The fact2() function returns the factorial of it's argument -- that's all you need to know about it.

Given that, do you have any problem understanding how the fact() function works?

If not, then you can replace fact2() with ANY function that does the same things... such as fact().

int fact(int n)
{
   if (n <= 1)
      return 1;
   return n * fact(n - 1);
}

To visualize how the recursion works, imagine that you have the fact() function printed on a wall for everyone to see. You also have a bunch of minions, named Fred, Sue, Bob, and Karen.

You get tasked with finding the factorial of 3.

YOU:
You write n=3 on an index card and pass it to Fred, telling him to evaluate the function, write the return value on an index card, and then return it to you.
You then wait until Fred returns the card to you before proceeding.

FRED:
Fred looks at the code and sees that n is not less than or equal to 1, so he calculates (n-1) and writes 2 on an index card and passes it to Sue, telling her to evaluate the function, write the return on an index card, and return it to him.
Fred then waits until Sue returns the card before proceeding.

SUE:
Sue looks at the code and sees that n is not less than or equal to 1, so she calculates (n-1) and writes 1 on an index card and passes it to Bob, telling him to evaluate the function, write the return value on an index card, and return it to her.
Sue then waits until Bob returns the card before proceeding.

BOB:
Bob looks at the code and sees that n is less than or equal to one, so he writes 1 on an index card and passes it back to Sue.

SUE:
Sue takes the index card that Bob passed back to her with the 1 written on it and then multiplies it by the value of n written on her other index card, which is 2, and gets a result of 2. She writes this on an index card and passes it back to Fred.

FRED:
Fred takes the index card that Sue passed back to him with the 2 written on it and then multiplies it by the value of n written on his other index card, which is 3, and gets a result of 6. He writes this on an index card and passes it back to you.

YOU:
You take the index card that Fred passed back to you with the 6 written on it and accept that as the value of fact(3).

Now, let's look at what YOU see in all of this:

You write n=3 on an index card and pass it to Fred, telling him to evaluate the function, write the return value on an index card, and then return it to you.
You then wait until Fred returns the card to you before proceeding.
You take the index card that Fred passed back to you with the 6 written on it and accept that as the value of fact(3).

There is NO magic here.

 

When I first learned about recursion, I thought it was the coolest thing ever. When I settled into my career in compiler development, I understood why. It was the sharpest tool in my box.

 

When I first learned about recursion, I thought it was the coolest thing ever. When I settled into my career in compiler development, I understood why. It was the sharpest tool in my box.

It's fine for things like tree and graph algorithms (functional programming) but I'd fire anyone that used it in a critical embedded applications operational logic.

 

https://forum.allaboutcircuits.com/threads/why-do-we-use-recursive-function.145874/post-1240875
https://jeremybytes.blogspot.com/2014/01/a-functional-fibonacci-sequence-as.html

 

I understand Fibonacci sequence, I'm having difficulty grasping the recursive mechanism used in this code.

#include <stdio.h>

int fib(int n) {
    if (n <= 1)
        return n;

    return fib(n - 1) + fib(n - 2); // Recursive case
}

int main() {
   
    printf("Fibonacci sequence: ");
    for (int i = 0; i < 6; i++) {
        printf("%d ", fib(i));
    }

    return 0;
}

• When i = 0, the value is 0.
• When i = 1, the value is 1.
• When i = 2, the value is 1.
• When i = 3, the value is calculated as fib(2) + fib(1)

Could you kindly provide some help into how the recursion works in this context, especially when i = 3 and beyond?

Just walk through it the same way I walked through the factorial problem. It's the exact same process.

When i = 3, you call fib(2), which you've already established returns 1. You also call fib(1), which you've already established returns (1). So you add them together, get 2, and that is what fib(3) returns, so that has been established.

When i = 4, you call fib(3) and fib(2), which we have already established return 2 and 1, respectively. Add them to get 3 and we have now established that fib(4) returns 3.

And so on, and so on.

 

Hello Everyone

I am trying understand the flow of recursive functions in the context of C language,

I've attempted to create a flowchart to visualize the execution of a recursive function, but I'm uncertain about certain aspects and would greatly appreciate your expertise to clarify them.


View attachment 314196

Just a word on terminology. Many books and articles describe a recursive function as "a function that can call itself". While technically valid, it can be confusing so think of it more as "a function that can call a copy of itself", while not technically correct it is easier for some people to grasp because ordinarily functions always call other distinct functions. @WBahn talks about this above.

Also the first thing any recursive function should do, is to decide it it's finished and return there and then, again @WBahn shows this above. Always think about the termination conditions and make sure the functions starts by checking those, if you gloss over this important detail its easy to code infinite recursion and that's hard as hell to debug.

Also some recursive function implementations use two functions, an outer function that your code calls and then an inner function that is recursive and is initially called by the outer function.

It might also be instructive to take a look at some functional languages, these languages inherently rely on recursion (these languages have no loop constructs for example) and they implicitly hold their state in the stacked local variables in each call (these languages have no variables either, think of the factorial function here).

As others have said a flowchart is not a great way to express a recursive solution to a problem, thinking of it in terms of a flowchart is possible but sort of hides some the reality.

Take a language like Scheme, it is extremely instructive to spend some time learning about this, even for C programmers.

 

It's fine for things like tree and graph algorithms (functional programming) but I'd fire anyone that used it in a critical embedded applications operational logic.

There are not typically compilers running on critical embedded processors. Though I do have one in my ballroom lighting server (PIC24, 512K program, 64K ram). I can write and send programs from my phone’s browser. And yes, it does use recursion.

 

There are not typically compilers running on critical embedded processors. Though I do have one in my ballroom lighting server (PIC24, 512K program, 64K ram). I can write and send programs from my phone’s browser. And yes, it does use recursion.

I don't have a problem with using recursion at the proper place and time. It's a convenient and elegant solution to a class of problems when you can have a unbounded stack. When you don't or have critical safety issues, use iteration. Recursion can always be replaced with basic iteration. Recursion and iteration are equally expressive.

 

Replacing recursion with iteration usually involves implementing a stack. Show me an algorithm for tree traversal (say, inorder) without using either iteration or a stack. Recursion is a silly way to implement factorial, which can trivially be done iteratively.

 

Replacing recursion with iteration usually involves implementing a stack. Show me an algorithm for tree traversal (say, inorder) without using either iteration or a stack.

Note, I said 'unbounded' stack, NOT, NO, STACK.

 

Note, I said 'unbounded' stack, NOT, NO, STACK.

Which can also be done with a recursive function. You just have check the depth. In compilers, the depth is usually related to the depth of nesting in the program, which really never gets out if control in a real program. The embedded compiler I referred to would have hit other limits long before depth of recursion could be a problem.

 

Which can also be done with a recursive function. You just have check the depth. In compilers, the depth is usually related to the depth of nesting in the program, which really never gets out if control in a real program. The embedded compiler I referred to would have hit other limits long before depth of recursion could be a problem.

This is basic data structures stuff. Recursion and iteration are equally expressive (but not always equally elegant) but there are other than mathematical and computer science restrictions on software being designed for things that can hurt or kill people and destroy valuable property.

https://betterembsw.blogspot.com/2014/07/dont-overflow-stack.html



Many of the security holes in software are related to stack overflows, out of bounds arrays, etc.. The bad actors know how to abuse these sorts of unbounded faults.

 

I've used and do use reentrant functions with my home software projects. For a 8-bit PIC project you have a choice usually.


If this project were to control something critical like emergency house power or security the 'compiled' stack stays the default choice.
https://microchipdeveloper.com/xwiki/bin/view/software-tools/xc8/non-reentrant/

To understand the reason why functions need to be duplicated, you need to know how variables are allocated memory in a data stack and the consequences of this allocation.

The MPLAB XC8 compiler uses a compiled data stack when the default stack model is selected. With this type of stack, local, stack-based variables (auto and parameter variables, as well as compiler-allocated temporary storage) are allocated a fixed address in data memory, much like the allocation of global objects. Since direct memory-access instructions can be used to read and write objects allocated in this way, this model can be used for all 8-bit PIC devices and yields very efficient code. The one problem this type of allocation presents is that functions that define local objects are not reentrant.

A reentrant function can have multiple instances of itself active at the same time. The common usage of reentrant functions is with recursion, where a function calls itself or calls a function that will ultimately lead to itself being called. So if the function foo() calls the function bar() and bar() calls foo(), then foo() (and bar() for that matter) need to be reentrant for this code to execute correctly.

For a function to be reentrant, each instance of itself must use its own copy of any local variables. However, since a compiled stack allocates local objects at a fixed address, the local variables of one instance of a function would be at the same address as the local variables used by another, so there would be a corruption of the function's local variables.

A function must also be reentrant if it is called from separate call graphs in a program. A call graph is a tree of function calls that constitute one sequential part of a program, much like a thread. Main-line code constitutes one call graph, and the code executed for an interrupt, another. If foo(), for example, has been written so that it does not use recursion, you can safely use this function anywhere in your program. But if foo() is called from main-line code and also from interrupt code, this could result in both instances being active at the same time, specifically, if foo() was executing in main-line code when an interrupt was triggered, then execution of that instance of foo() would be suspended and a second instance would be executed by the interrupt, corrupting the variables of the original instance.

If your project is set up to use the compiled stack, recursion is not supported. If you attempt to recursively call a function you will get the following error message:

recursive function call to "_foo"

 

I don't have a problem with using recursion at the proper place and time. It's a convenient and elegant solution to a class of problems when you can have a unbounded stack. When you don't or have critical safety issues, use iteration. Recursion can always be replaced with basic iteration. Recursion and iteration are equally expressive.

There is a concept called tail recursion, where the implicit stack is not required and so stack capacity is not an issue.

https://www.geeksforgeeks.org/tail-recursion/

I think (but don't know for certain) that any non tail recursive function can always be rewritten as a tail recursive form.

It's also true that iterative (Turing machine) and recursive (Lambda calculus) are equivalent, it seems that functional (lambda calculus) languages lead to fewer bugs, by avoiding mutation these languages can eliminate subtle problems especially when being parallelized.

 

This is an interesting read.

https://www.highgear.com/blog/why-we-chose-to-write-important-code-in-f-sharp/

and this too

https://www.janestreet.com/technology/