Рекурсия, Хвостовая рекурсия и итерация - PullRequest
Новая
       14

Рекурсия, Хвостовая рекурсия и итерация

1 голос
/ 10 сентября 2011

Вот мой код.

Рекурсия: 

#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);
}

Итерация 

#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);
}

Теперь мои сомнения:

  1. Iпрочитайте это, чтобы перейти от рекурсии к итерации, вам нужно использовать стек и продолжать выдвигать данные, а затем извлекать их позже.Сейчас я не вижу здесь этого.Зачем?Когда используется стек, а когда нет?
  2. Верен ли здесь мой перевод на итеративную версию?Является ли этот хвост рекурсивным, потому что так сказал источник кода Recursion.
  3. Как перейти с рекурсивной версии на итеративную.Мне действительно нужен хороший источник, откуда я мог бы изучить это.Поиск в Google не сильно помог.

Ответы [ 2 ]

3 голосов
/ 10 сентября 2011

1) Вам нужно использовать стек, когда есть значения для сохранения для каждого вызова. В вашем случае вы не используете значения из более глубоких рекурсивных вызовов после рекурсивного вызова, поэтому в стеке нечего сохранять.

2) Это хвостовая рекурсия, если вызов самому себе является последним, что он делает. В комментариях @leppie вы выполняете 2* после последнего вызова метода.

3) Общий подход заключается в использовании стека; однако в этом случае в стеке нечего сохранять, поэтому вы можете удалить его.

Вот несколько примеров, один из которых требует стека, а другой использует хвостовую рекурсию и не использует. 

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.
}
0 голосов
/ 10 сентября 2011

Вы должны знать, что рекурсия хвоста более оптимизирована, чем рекурсия.Компилятор знает, что это рекурсия и может изменить некоторые вещи.

...