Recursive functions in C

Question

I'm trying to understand recursion. Specifically there are 2 functions I can't get.

The first one is an example I came across on the Web:

#include <stdio.h>

void printnum(int begin) {
printf("%d", begin);

if (begin < 9) {                      
    printnum(begin + 1); 
}

printf("%d", begin);
}

void main() {
    printnum(1);
}

The output of this function is: 123456789987654321

I can understand how it reaches from 1 to 9, however what I don't get is how it goes backwards if there's no value decrease anywhere. So how? O.o

The second function I can't get is something I came up with:

#include <stdio.h>

int dbl(int i) {
    if (i == 1) {
        return 1;
    }

    return dbl(i - 1) + dbl(i - 1);
}

void main() {
    int i;

    for (i = 1; i < 10; i++) {
        printf("%d\t", dbl(i));
    }
}

So, this one prints something like: 1 2 4 8 16 32 64 128 256

It's so confusing, there are 2 calls to the function inside the same function, and I can't understand the logic behind this. What is the exact process the function goes through to print the double of each number?

Answer 1

The simplest way to explain your question: what I don't get is how does it go backwards if there's no value decrease anywhere, is to use a debugger, place a break point in the spot indicated, and watch what happens as the function execution stack unwinds.

void printnum(int begin) {
    printf("%d", begin);

    if (begin < 9) {                      
        printnum(begin + 1); 
    }  //place break point here, and single step through rest of code.  
       //You will see execution flow will bounce back and forth from here....

    printf("%d", begin);  //....to here as the function "unwinds" from recursion.
}  

Answer 2

To the first example:

First your begin variable is 1 and gets printed directly (printf("%d", begin);).

The if statement is called your recursion anchor. 8 times the begin variable has a value lower than 9, so the function printnum produces a call stack like this:

printnum(2);
printnum(3);
printnum(4);
printnum(5);
printnum(6);
printnum(7);
printnum(8);
printnum(9);

Now remember the recursion anchor: The begin variable is now 9, so recursion is skipped and the second print command printf("%d", begin); is executed from 9 backwards to 1.

EDIT: Second example

There the if statement is your recursion anchor, too, which results true on the first call in your for loop.

If dbl is called with 2, it returns the addition of dbl(1) + dbl(1), which results in 2.

If it's called with 3 it returns the addition of dbl(2) + dbl(2), which results in

(dbl(1) + dbl(1))
        +
(dbl(1) + dbl(1))

, which finally results in 4.

Hope it helps =)

Answer 3

The printnum(begin) function does this:

• first it prints the number begin
• then it calls printnum(begin+1) to do all the printing of larger numbers
• then it prints another begin

So the first and last thing it does is printing it's number, and in between that all the higher numbers are printed.

For the second function, you can think about it like this:

• What is db(1)? It's 1. No recursion involved.
• What is db(2)? It's db(1) + db(1). This is 1+1 = 2, since we already know that db(1) is 1.
• What is db(3)? It's db(2) + db(2). Since we know that db(2) equals 2, this is 4.
• What about db(4)? Since we know that db(3) is 4, db(4) ends up being 8.

And so on. One can see that each time the result doubles, since db(n) = db(n-1) + db(n-1) = 2*db(n-1)

Answer 4

Recursive function is a function that calls ITSELF again and again.

Imagine you have a round container where you have to put plates. You put the first plate in, then the second, then the third and so on. To get to the first plate, you will need to remove all the plates that are towering over it.

Same way when you call a recursive function, it executes something and then calls itself again. Now the second instance of the function is being executed and the first instance is at pause. The second instance now calls the third instance. the third will execute completely and then exit, now the control shifts back to the second instance. The second instance in now finished and the control turns back to the first instance. Now the first instance will be terminated.

This is how recursion occurs.

For example, suppose you have to calculate factorial of a number:

int fact(int n){

if(n==1)
return 1;

else 
return n*fact(n-1);

}

void main(){

printf(fact(3));
}

this will print 6. it works like this:

fact(3) will return 3*fact(2). fact(2) will return 2*fact(1). fact(1) will return 1.

so the statement will actually look like--> 3*(fact(2))--> 3*(2*fact(1)). which will come down to 3*2*1.

Hope this helps.

Answer 5

For the first recursive function, just imagine this function without a recursive call.

   printnum(1);

would output

   11

But when you recursively call that function, the second print method does not get called until all recursive calls have finished. In this case, you have 9 recursive calls. So the the function must execute itself (up to the recursive call, meaning just the first print statement) 9 times before it can reach the second part of the recursize function. So for output 123456789, only these lines get called:

printf("%d", begin);

if (begin < 9) {                      
printnum(begin + 1); 
 }

but then once you reach 9, the other recursive calls finish, executing the following code 9 times:

  printf("%d", begin);

giving you the second half of your output 987654321.

Answer 6

Here's the gist of what happens when you call a function:

The code you are running pauses and the function starts running. When the function ends, the code that was paused restarts where it was.

main:
   code
   code
   function    ----->  function:
              <-----     print
   code            ----  return

That same thing happens with recursion, it just happens on multiple levels:

main:
   code
   code
   function    ----->  function:
              <-----     print
                   -     function  ----->  function :
                   -               <----     print
                   -                   -     print
                   -                   ----  return
                   -     print
   code            ----  return

That's why it "goes back down". It's never subtracting or lessening or anything, its just the second part of the function executing after the level below it has finished.

Answer 7

It doesn't actually decrease because the function remains on the stack until it is finished.

You have two calls to print the value of begin:

void printnum(int begin) {
    printf("%d", begin); //here

    if (begin < 9) {                      
        printnum(begin + 1); 
    }

    printf("%d", begin); //and here
}

The original call starts and ends with the same value, because you're not passing by reference, you're passing the value of begin + 1 to printnum. begin keeps its original value in the scope it existed in, so it doesn't 'decrease', rather the nested function calls begin coming off the stack and performing their second printf function.

It's somewhat like this in pseudocode.

call printnum(begin=1)
print(begin)    //prints '1'
begin < 9 //True
call printnum(begin + 1) //now begin=2
    print(begin) //prints '2'
    begin < 9 //True
    call printnum(begin + 1) //now begin=3
        ...
        //etc until begin is not less than 9
        //upon which the PREVIOUS calls continue their work
        ...
        second print(begin)//in this scope, begin=3
        end
    second print(begin)//in this scope, begin=2
    end
second print(begin)//in this scope, begin=1
end

Answer 8

For the first:

The "printing of backward numbers" comes from the second print statement in the recursive function. When begin is 9 in the ninth recursive call, the if statement fails and the recursion ends. It then goes on to print 9 and exits that particular recursive call, and return to the previous recursive call, where begin is 8. Keeping in mind that all the way up now we are at the end of the if statement. Then we exit the 8th recursive call, and return to where begin is 7, and so on.