Recursive Function with two calls-CodePudding

Here I've a code about recursion from geeksforgeeks.com

#include<stdio.h>
void fun(int x)
{
  if(x > 0)
  {
     fun(--x);
     printf("%d\t", x);
     fun(--x);
  }
}
 
int main()
{
  int a = 4;
  fun(a);
  return 0;
}

I am really getting lost myself, I cannot understand working principle of this function. As far as I know, firstly the recursive each call of the function are stored in stack and is being started popping after base case reached. However, I cannot understand how it works after the printf function which the second call. Can anyone please explain me? I'm very pleased, if so. Thanks in advance for your lovely contributions.

CodePudding user response：

The x variable in fun(x) is local, and first call is x-1, second is x-2

Consider the simplest case

fun(1)

Results in fun(0) and fun(-1) being called

fun(2)

Results in fun(1) and fun(0) being called, and since 1 is > 0, fun(1) will also invoke fun(0) and fun(-1) before fun(2) calls fun(0)

Here's a partial call stack, indented according to which function is calling

fun(4)
  fun(3)
    fun(2)
      fun(1)
        fun(0)
        print
        fun(-1)
      print
      fun(0)
    fun(1)
      fun(0)
      print
      fun(-1)
    print
    fun(0)
  fun(2)
...

CodePudding user response：

The detail below illustrates the call depth using indents and shows calls to fun and printf to illustrate the execution sequence and print output:

Line 15: fun(4)                       --> depth 1 
    Line 6: x=3, fun(3)               --> depth 2
        Line 6: x=2, fun(2)           --> depth 3
            Line 6: x=1, fun(1)       --> depth 4
                Line 6: x=0, fun(0)   --> depth 5, do nothing & return
                Line 7: printf        --> "0"
                Line 8: x=-1, fun(-1) --> depth 5, do nothing & return
                Return                --> depth 3
            Line 7: printf            --> "1"
            Line 8: x=0, fun(0)       --> depth 4, do nothing & return
            Return                    --> depth 2
        Line 7: printf                --> "2"
        Line 8: x=1, fun(1)           --> depth 3
            Line 6: x=0, fun(0)       --> depth 4, do nothing & return
            Line 7: printf            --> "0"
            Line 8: x=-1, fun(-1)     --> depth 4, do nothing & return
            Return                    --> depth 2
    Line 7: printf                    --> "3"
    Line 8: x=2, fun(2)               --> depth 2
        Line 6: x=1, fun(1)           --> depth 3
            Line 6: x=0, fun(0)       --> depth 4, do nothing & return
            Line 7: printf            --> "0"
            Line 8: x=-1, fun(-1)     --> depth 4, do nothing & return
            Return                    --> depth 2
        Line 7: printf                --> "1"
        Line 8: x=0, fun(0)           --> depth 3, do nothing & return
        Return                        --> depth 1
    Return                            --> depth 0

CodePudding user response：

First of all, I recommend you to read a book about recursion, for example the books of Rozsa Peter or Daniel Friedman (The little schemer) or better take some first year course/mooc of introduction. After that you can study more advanced stuff.

You have this code:

void fun(int x)
{
  if(x > 0)
  {
     fun(--x);
     printf("%d\t", x);
     fun(--x);
  }
}

Suppose you call fun(4).

In this case you have a sigma-recursive operator (also called primitive recursion). The recursion needs some limit cases. In this case it is a simple linear recursion with only the case "counter reaches null value" (the same as in the definition of arithmetics of Peano).

If it reaches 0, it finished. Otherwise, it calls itself with the counted decremented by 1 toward the limit case and stacks 2 more calls:

 printf("%d\t", x);
 fun(--x);

The last call is in tail position, so it does nothing, it modified a local variable that is not used any longer. So your function reduces to this:

void fun(int x)
{
  if(x > 0)
  {
     fun(--x);
     printf("%d\t", x);
  }
}

As the other answers say, this function will stack some calls and I do not reproduce any more the stack that is present in the other answers.

Practically,

it calls itself for f(4),
then f(3),
then f(2),
then f(1),
then f(0) is the limit case,
then it returns to the stacked printf from f(1), and PRINTS 1,
then it returns to the stacked printf from f(2), and PRINTS 2,
then it returns to the stacked printf from f(3), and PRINTS 3,
then it returns to the stacked printf from f(4), and PRINTS 4.