CODEWITHSUNDEEP
crecursioniterationtail-recursion
Kraken
Kraken

Reputation: 24213

Recursion, Tail Recursion and Iteration

Here is my code.

Recursion:

#include <stdio.h>

int Recursion(int m,int n)
{
    if(m==0 || n==0)
        return 1;
    else
        return 2*Recursion(m-1,n+1);
}

void main()
{
    int m,n,result;
    m=3;
    n=-2;
    result=Recursion(m, n);
    printf("%d",result);
}

Iteration

#include <stdio.h>

int Recursion(int m,int n)
{
    int returnvalue=1;
    while(m!=0 && n!=0)
    {
        returnvalue=returnvalue*2;
        m--; n++;
    }
    return returnvalue;
}

void main()
{
    int m,n,result;
    m=3;
    n=-2;
    result=Recursion(m,n);
    printf("%d",result);
}

Now my doubts are:

  1. I read that to change from recursion to iteration, you need to use a stack and keep pushing the data and popping later. Now I don't see doing it here. Why? When is stack used, and when is it not?
  2. Is my translation to an iterative version correct here? Is this tail recursive because the source of the Recursion code said so.
  3. How do I change from a recursive version to an iterative one. I would really need a nice source from where I can study this. Googling did not help much.

Upvotes: 1

Views: 707

Answers (2)

Peter Lawrey
Peter Lawrey

Reputation: 533520

1) You need to use a stack when there are values to save for each call. In your case, you don't use the values from deeper recursive calls after the recursive invocation so there is nothing to save on the stack.

2) It's tail recursion if the call to itself is the last thing it does. As @leppie comments, you are performing a 2* after the last method call.

3) The general approach is to use a stack; however, in this case, there is nothing to save on a stack, so you can drop it.

Here are some examples, one which requires a stack and another which uses tail recursion and does not.

void reverseCounting(int i, int n) {
    if (i >= n) return;
    reverseCounting(i + 1, n);
    cout << i << endl;
}

void counting(int i, int n) {
    if (i >= n) return;
    cout << i << endl;
    counting(i + 1, n);
}

// you could just count backwards, but this is a simple example.
void reverseCountingLoop(int i, int n) {
    // for C you can write you own stack to do the same thing.
    stack<int> stack; 
    //// if (i >= n) return;
    while (!(i >= n)) {
        //// reverseCounting(i + 1, n);
        // save i for later
        stack.push(i);
        // reuse i
        i = i + 1;
    }
    // unwind the stack.
    while (!stack.empty()) {
        //// cout << i << endl;
        i = stack.top(); stack.pop();
        cout << i << endl;
    }
}

void countingLoop(int i, int n) {
    //// if (i >= n) return;
    while (!(i >= n)) {
        //// cout << i << endl;
        cout << i << endl;
        //// counting(i + 1, n);
        // reuse i
        i = i + 1;
    }
    //// nothing after the recursive call.
}

Upvotes: 3

mathieug
mathieug

Reputation: 901

You should know a tail recursion is more optimized than recursion. Compiler know it's a recursion and may change some things.

Upvotes: 0

Related Questions