cs202ch10

2021-09-04 来源：欧得旅游网

C Language (CS202) SECTION <10.1>

RECURSION

RECURSION vs ITERATION

FACTORIAL { n! = n * (n-1) * (n-2) * .. * 1 } #include

long factorial(int num);

void main()

{ int num; long fact;

printf(\"Enter a number : \"); scanf(\"%d\ if (num >= 0)

printf (\"Factorial %d is %ld\\n\factorial(num) ); }

<1> Function using Iteration : long factorial(int num)

{ long fact=1; // 0!=1, 1!=1

while(num > 1)

{ fact=fact*num; num--; } return fact; }

main : factorial(4) <2> Function using Recursion :

long factorial(int num) function: { factorial(4) if (num==1 || num==0) return( 4 * factorial(4-1)) return 1; factorial(3) else return( 3 * factorial(3-1)) return (num * factorial(num-1)); factorial(2) } return( 2 * factorial(2-1)) factorial(1) terminating case return 1 num=0 || num==1 general case

5 * 4!

Recursion :

 A recursive function is a function that calls itself either directly or indirectly through another function.

 The function actually knows how to solve only the base case (terminating case). If a function is called with a base case, the function simply returns a result.

Difference Between Iteration and Recursion :

 Any problem that can be solved recursively can be solved iteratively (using while loop)

 Both recursion and iteration involve repetition.

 Iteration keeps modifying a counter until the condition fail.

 Recursion keeps producing simpler versions of the original problem until the base case is reached.

 Both iteration and recursion can cause infinite loop

 Iteration : if the loop-condition never become true

 Recursion : if recursion step does not reduce the problem to the base case.

 Recursive calls take time and consume additional memory.

(Each recursive call causes another copy of the function to be created)

 Recursive calls is chosen when iterative solution is not apparent in solving the problem and using recursive calls is easier to understand and debug

NOTE : long factorial(int num) { if (num==1 || num==0) return 1; else

return (num * factorial(num-1)); }

Consider

<1> return (num * factorial(num--)); right / wrong

<2> return (num * factorial(--num)); right / wrong

ADDING ODD NUMBERS

// The program calculate the totals of 1 adds up to an odd number

#include

long add_odd(int num);

main() { int num;

do { printf(\"Enter a positive odd number : \"); scanf(\"%d\

if (num%2 == 0 || num <1 )

printf(\"\\n\\a Error: You have to enter POSITIVE ODD number\\n\"); }while(num%2 == 0 || num<1);

printf(\"Add odd numbers from 1 to %d is : %ld\\n\add_odd(num) ); return 0; }

<1> Function Using Iteration :

long add_odd(int num) { long total=1;

while(num>1)

{ total = total+num; num- =2; }

return total; }

main : add_odd(5) <2> Function Using Recursion :

function: long add_odd(int num) add_odd(5) { if (num == 1) return( 5 + add_odd(5-2) ) return num; else add_odd(3) return ( num + (add_odd(num-2)) ); return(3 + add_odd(3-1)) } add_odd(1) terminating case return 1 num==1

general case

add_odd(5) 5 + add_odd(3)

C Language (CS 202) SECTION <10.2>

EXERCISES

ADDING all ODD Numbers from X to Y

#include

long add_odd(int start, int end);

void main() { int start, end;

do { printf(\"Enter 2 odd numbers : \"); scanf(\"%d%d\ if(start%2==0 || end%2==0)

printf(\"\\n\\aERROR: You have to enter two ODD number\\n\"); if(start>end)

printf(\"\\n\\aERROR: The 1st number should be smaller than the 2nd one\\n\"); }while(start%2==0 || end%2==0 || start>end);

printf(\"Add odd number from %d to %d is : %ld\\n\add_odd(start, end) ); }

<1> Function Using Iteration : long add_odd(int start, int end) { long total=0;

while(start<=end)

{ total=total+start; end+=2; }

return total; }

main : add_odd(-1,5) <2> Function Using Recursion : long add_odd(int start, int end) function {

}

X To The POWER Of Y Question : Following is a program to calculate x to the power of y using iteration. Rewrite the iterative function( power() ) by a recursive function.

#include

void get_input(int *base, int *pow); double power(int base, int pow);

main() {

int base, pow, temp=0; double total;

get_input(&base, &pow); if (pow<=0 && base==0)

printf(\"The result is undefined\\n\"); else

{ if (pow<0)

total=power(base, -pow); else

total=power(base, pow); if (pow<0) total=1/total;

printf(\"%d to the power of %d is %lf\\n\" ,base, pow, total); }

return 0; }

OUTPUT : Enter Base : -> 2 Enter Base : -> -2

Enter Power : -> 7 Enter Power : -> -2

2 to the power of 7 is 128.000000 -2 to the power of 2 is 0.250000

Function Using Recursion :

double power(int base, int pow) main : power(2,3) { function :

}

More On RECURSION

#include #include

void reverse(char *string, int size);

main()

{ char string[20];

gets(string);

reverse(string, strlen(string)); printf(\"%s\\n\ return 0; }

main : reverse(“abcde”, 5) function : string reverse(“abcde”, 5) void reverse(char *string, int size) { char temp; a b c d e \\0 e b c d a \\0

if (size<2) [0] [1] [2][3] [4][5] [0][1] [2] [3] [4][5] return;

else string reverse(“bcda”, 3) { temp=string[0]; string[0]=string[size-1]; e b c d a \\0 e d c b a \\0

string[size-1]=temp; [0][1] [2][3] [4][5] [0][1] [2] [3][4][5] reverse(string+1, size-2);

} string reverse(“cda”, 1) }

e b c d a \\0 e d c b a \\0

[0][1] [2][3] [4][5] [0] [1] [2] [3][4][5]

terminating case : size of string == 0/1

[0] [1] [2] … [ ] [size-1] general case : reserve(string+1, size-2)

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部栏目

cs202ch10