Алгоритм рекурсии - PullRequest
Новая
       4

Алгоритм рекурсии

3 голосов
/ 02 декабря 2011

Я всегда растерялся, когда пишу рекурсивную программу, даже маленькую. 

#include <iostream>
using namespace std;

int recursion(int x)
{
    if(x == 0)
        return 0;

    return (x + recursion(x-1));  //recursive function call should always be in the                                        return statement?
}

int main()
{
    cout<<"SUM:"<<recursion(9);
}

Есть ли другой способ, с помощью которого рекурсивный вызов функции не может быть в операторе возврата

Ответы [ 4 ]

7 голосов
/ 02 декабря 2011

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

Например: 

int recursion(int x)
{
    if (x == 0) return 0;
    int rec = recursion(x-1);
    return x + rec;
}

Тем не менее, выполнение рекурсивного вызова в самом конце функции имеет свои преимущества: это называется "хвостовой рекурсией", и хороший компилятор может оптимизировать удаленную хвостовую рекурсию.

Наконец, стоит упомянуть, что в вашем конкретном примере (суммирование чисел от 0 до n) рекурсия совершенно не нужна.

3 голосов
/ 02 декабря 2011

При выполнении рекурсии не думайте о рекурсии. Подумайте: «Ах, на этом этапе было бы целесообразно назвать эту recursion() функцию» или «О, я мог бы использовать ее здесь снова» . Они являются обычными вызовами функций, как и все остальные вызовы.

Рекурсия Термин излишне смущает многих будущих программистов. Если вы понимаете функции и вызовы функций, вы уже понимаете рекурсию, вы просто еще не знаете.

3 голосов
/ 02 декабря 2011

Вы можете, конечно, рекурсировать любым способом, который вам нравится. Например, чтобы вычислить числа Фибоначчи наивным способом, у вас есть рекурсия, которая обязательно очень быстро разветвляется: 

inf fib(int n)
{
  //... base case
  int a = fib(n - 1);
  int b = fib(n - 2);
  return a + b;
}

Вы также можете написать return fib(n-2) + fib(n-1);, но дело в том, что вы не можете устранить рекурсивное ветвление в этом случае.

С другой стороны, то, что вы действительно хотите попытаться достичь, - это tail рекурсия, с помощью которой последнее утверждение является не чем иным, как рекурсивным вызовом. Например, ваше суммирование может быть записано как: 

void sum(int n, int & result)
{
  if (n = 0) return;
  result += n;
  sum(n - 1, result);
}

Ключевой особенностью этого особого случая является то, что рекурсия может происходить полностью на месте. Как правило, стек увеличивается как ( B & minus; 1) n , где n - глубина рекурсии, а B - количество параллельных оценок. Это экспоненциально (читай: плохо ), , если только не имеет B = 1, и в этом случае можно попытаться спроектировать функцию как хвостовую рекурсию. *

0 голосов
/ 02 декабря 2011

Вам не нужно помещать рекурсивный вызов функции в оператор return;Вы можете просто сделать: 

int recursion(int x)
{

    if(x == 0)
        return 0;
    int val = recursion(x-1);
    return (x + rec);  
 }
...