Scribd
Upload
18 views2 pages

Structural vs Generative Recursion

The document discusses two types of recursion: structural and generative. Structural recursion uses part of the original input as an argument in recursive calls, while generative recursion computes new data as the input for each call. As an example, a recursive method that returns rec(n+1) is structural and direct recursion because it uses a part of the original input n. Meanwhile, a method that returns gcdRec(b, a % b) is generative and direct recursion because it uses the new value of a % b rather than the original inputs a and b.

Uploaded by

para sa project
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
18 views2 pages

Structural vs Generative Recursion

The document discusses two types of recursion: structural and generative. Structural recursion uses part of the original input as an argument in recursive calls, while generative recursion computes new data as the input for each call. As an example, a recursive method that returns rec(n+1) is structural and direct recursion because it uses a part of the original input n. Meanwhile, a method that returns gcdRec(b, a % b) is generative and direct recursion because it uses the new value of a % b rather than the original inputs a and b.

Uploaded by

para sa project
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Laoag City, Ilocos Norte

Structural vs Generative Recursion

Difference in recursive call is not the only way recursive forms are grouped. By looking
at how a method manipulates input data, we can group forms into
either structural or generative.

Structural

Structurally recursive methods use part of the original input as a passed argument.

For example, our previous example could be further described as both structural and
direct recursion as the method uses a part, n+1, of the original input, n

1 int rec(int n)
2 {
3 if (n == 10) //base case
4 return 1;
5 else
6 return rec(n+1); //structural, direct recursion
7 }
8

Generative

Generative recursive methods on the other hand compute or “generate” new


data as the input for each recursive call.

In this example of the Euclidean algorithm, we can see that gcdRec is generative
because it uses the modulo of a and b rather than a or b themselves.

CpE 311L/L SOFTWARE DESIGN


Prepared by: Engr. Mariscel Lived De Guzman
Page 1 of 2
Laoag City, Ilocos Norte

1 int gcdRec(int a, int b) {


2 if (b == 0) return a; //base case
3 return gcdRec(b, a % b); //generative, direct recursion
4 }
5

CpE 311L/L SOFTWARE DESIGN


Prepared by: Engr. Mariscel Lived De Guzman
Page 2 of 2

You might also like