Линейная и древовидная рекурсии

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

Пример 5. Написать рекурсивное определение возведения числа x в степень n:

Базисное утверждение: x⁰=1;

Рекурсивное утверждение:     xⁿ=x*xⁿ-1;

Определим 3⁵

3⁵= 3⁴*3

3⁴= 3³*3

…….

3⁰=1.

 

Рисунок 5 – Схема процесса вычисления 5 степени тройки

Как видно из рисунка, сначала выполняется рекурсивный спуск, который определяется формулой рекурсивного утверждения и сопровождается вызовом рекурсивной функции (ее очередной активации). После выполнения базисного утверждения, определяющего конец рекурсивных вызовов, происходит возврат управления с одновременным вычислением значения по формулам рекурсивного утверждения. Этот процесс называется рекурсивным подъемом. Именно рекурсивный подъем формирует искомый результат.

Текст программы:

#include "stdafx.h"            

#include <stdio.h>

Long int  funstep(int x,int n)

{

if (n==0) return 1;

   else

  { 

   return x*funstep(x,n-1);

}

}

int main(int argc, char* argv[])

{

int x,n;

 puts("input x,n for x^n");

 scanf("%d %d",&x,&n);

 printf("\n %7d ^ %3d =",x,n);

 printf("%10d\n",funstep(x,n));

return 0;

}

Однако, есть рекурсивные определения, при вычислении по которым на каждой активации необходимо вычисление двух и более  выражений, требующих дополнительного вызова рекурсивной подпрограммы. Такие рекурсии получили название древовидных. Простейшим примером древовидной рекурсии является вычисление заданного  числа Фибоначчи.

Пример 6. Написать программу, которая вычисляет число Фибоначчи по его номеру. По определению последовательность  1 1 2 3 5 8 13 21 34 55 89 ….получила название чисел Фибоначчи. Первые два числа равны 1 (F1=1, F2=1), а остальные, начиная со второго, вычисляются по следующей схеме: Fn=Fn-1+Fn-2. Эта процедура может быть легко описана с помощью рекурсии. При этом:

Базисное утверждение: F1=1 и F2=1

Рекурсивное: Fn=Fn-1+Fn-2

Найдем значение 6-го числа Фибоначчи. Схема вычисления выглядит так:

F6=   F5                          +                       F4

F5=   F4           +          F3;                   F4=F3 +   F2;

F4=F3 + F2                F3=F2 + F1;     F3=F2 + F1    F2=1

F3=F2+F1; F2=1;             F2=1; F1=1;     F2=1; F1=1;          

 F2=1, F1=1.

В этом случае тоже сначала выполняется рекурсивный спуск, однако, на каждой активации рекурсивной подпрограммы необходимо два вызова этой подпрограммы. Поэтому, и рекурсивных спусков, и рекурсивных подъемов здесь несколько. То есть, последовательность вызовов подпрограммы представляет собой дерево, а значит, это древовидная рекурсия. Дерево этой рекурсии представлено на рисунке 6.

 

     Рисунок 6 – Дерево вычисления числа Фибоначчи

Тело программы вычисления числа Фибоначчи:

#include "stdafx.h"

#include <stdio.h>

Int fib(int n)

{

if((n==1)||(n==2)) return 1;

else

{ return fib(n-1)+ fib(n-2);}

}

int main(int argc, char* argv[])

{ int n;

puts("input n value Fibonnachi");

scanf("%d",&n);

 printf("\n %7d Fibonachi =",n);

 printf("%10d\n",fib(n));

return 0;

}

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