CS计算机代考程序代写 Microsoft PowerPoint - 15_Recursion_SHORT.pptx

Microsoft PowerPoint – 15_Recursion_SHORT.pptx

CS 2211
Systems Programming

Recursion

Recursive Definitions

• Recursion:
defining something in terms of itself

• Recursive definition

– Uses the word or concept being defined in the
definition itself

– Includes a base case that is defined directly, without
self-reference

Recursive Definitions

• A recursive definition consists of two parts:
– The base case: this defines the “simplest” case or starting

point

– The recursive part: this is the “general case”, that
describes all the other cases in terms of “smaller” versions
of itself

• Why is a base case needed?
– A definition without a non-recursive part causes

infinite recursion

Recursive Definitions
• Mathematical formulas are often expressed recursively

• Example: the formula for factorial
for any positive integer n, n! (n factorial) is defined to be
the product of all integers between 1 and n inclusive

• Express this definition recursively

1! = 1 (the base case)
n! = n * (n-1)! for n>=2

• Now determine the value of 4!

1 2

3 4

8-5

Discussion
• Recursion is an alternative to iteration, and can be a very

powerful problem-solving technique

• What is iteration? repetition, as in a loop

• What is recursion? defining something in terms of a smaller
or simpler version of itself (why smaller/simpler? )

8-6

Recursive Programming
• Recursion is a programming technique in which a method can

call itself to solve a problem

• A function in C that invokes itself is called a
recursive method
and must contain code for

– The base case
– The recursive part

8-7

Example of Recursive Programming
• Consider the problem of computing the sum of all the

numbers between 1 and n inclusive

e.g. if n is 5, the sum is (in an iterative processes)
1 + 2 + 3 + 4 + 5

• How can this problem be expressed recursively?
Hint: the above sum is the same as

5 + 4 + 3 + 2 + 1

Recursion in C

END OF Part 1

5 6

7 8

#include

int SumIter(int );

int main()
{

int i = 3 , x;

x = SumIter(i);
printf(“\nIteration x: %d\n”, x);

return 0;
}

int SumIter(int ir)
{

if (ir == 1)
return (1);

else
{

int totalSum = 0;
for (int k = 1; k <= ir; k++) { totalSum = totalSum + k; } return (totalSum); } } Label Address Value 399 … … … … … … … … … … … … … … #include

int SumIter(int );

int main()
{

int i = 3 , x;

x = SumIter(i);
printf(“\nIteration x: %d\n”, x);

return 0;
}

int SumIter(int ir)
{

if (ir == 1)
return (1);

else
{

int totalSum = 0;
for (int k = 1; k <= ir; k++) { totalSum = totalSum + k; } return (totalSum); } } Label Address Value 399 i 400 - 403 3 x 404 - 407 … … … … … … … … … … … … #include

int SumIter(int );

int main()
{

int i = 3 , x;

x = SumIter(i);
printf(“\nIteration x: %d\n”, x);

return 0;
}

int SumIter(int ir)
{

if (ir == 1)
return (1);

else
{

int SumIter(int );

int main()
{

int i = 3 , x;

x = SumIter(i);
printf(“\nIteration x: %d\n”, x);

return 0;
}

int SumIter(int ir)
{

if (ir == 1)
return (1);

else
{

int totalSum = 0;
for (int k = 1; k <= ir; k++) { totalSum = totalSum + k; } return (totalSum); } } Label Address Value 399 i 400 - 403 3 x 404 - 407 ir 440 - 443 3 … … … … … … … … … … … 9 10 11 12 4 #include

int SumIter(int );

int main()
{

int i = 3 , x;

x = SumIter(i);
printf(“\nIteration x: %d\n”, x);

return 0;
}

int SumIter(int ir)
{

if (ir == 1)
return (1);

else
{

int totalSum = 0;
for (int k = 1; k <= ir; k++) { totalSum = totalSum + k; } return (totalSum); } } Label Address Value 399 i 400 - 403 3 x 404 - 407 ir 440 - 443 3 totalSum 444 - 447 0 … … … … … … … … … … #include

int SumIter(int );

int main()
{

int i = 3 , x;

x = SumIter(i);
printf(“\nIteration x: %d\n”, x);

return 0;
}

int SumIter(int ir)
{

if (ir == 1)
return (1);

else
{

int totalSum = 0;
for (int k = 1; k <= ir; k++) { totalSum = totalSum + k; } return (totalSum); } } Label Address Value 399 i 400 - 403 3 x 404 - 407 ir 440 - 443 3 totalSum 444 - 447 0 k 448 - 451 1 … … … … … … … … … #include

int SumIter(int );

int main()
{

int i = 3 , x;

x = SumIter(i);
printf(“\nIteration x: %d\n”, x);

return 0;
}

int SumIter(int ir)
{

if (ir == 1)
return (1);

else
{

int SumIter(int );

int main()
{

int i = 3 , x;

x = SumIter(i);
printf(“\nIteration x: %d\n”, x);

return 0;
}

int SumIter(int ir)
{

if (ir == 1)
return (1);

else
{

int totalSum = 0;
for (int k = 1; k <= ir; k++) { totalSum = totalSum + k; } return (totalSum); } } Label Address Value 399 i 400 - 403 3 x 404 - 407 ir 440 - 443 3 totalSum 444 - 447 6 k 448 - 451 1 … … … … … … … … … 13 14 15 16 5 Label Address Value 399 i 400 - 403 3 x 404 - 407 6 … … … … … … … … … … … … #include

int SumIter(int );

int main()
{

int i = 3 , x;

x = SumIter(i);
printf(“\nIteration x: %d\n”, x);

return 0;
}

int SumIter(int ir)
{

if (ir == 1)
return (1);

else
{

int totalSum = 0;
for (int k = 1; k <= ir; k++) { totalSum = totalSum + k; } return (totalSum); } } Label Address Value 399 i 400 - 403 3 x 404 - 407 6 … … … … … … … … … … … … #include

int SumIter(int );

int main()
{

int i = 3 , x;

x = SumIter(i);
printf(“\nIteration x: %d\n”, x);

return 0;
}

int SumIter(int ir)
{

if (ir == 1)
return (1);

else
{

int totalSum = 0;
for (int k = 1; k <= ir; k++) { totalSum = totalSum + k; } return (totalSum); } } OUTPUT: Iteration x: 6 #include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399
…
…
…
…
…
…
…
…
…
…
…
…
…
…

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407

…
…
…
…
…
…
…
…
…
…
…
…

17 18

19 20

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407

…
…
…
…
…
…
…
…
…
…
…
…

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

…
…
…
…
…
…
…
…
…
…
…

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
…
…
…
…
…
…
…
…
…
…

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
…
…
…
…
…
…
…
…
…
…

21 22

23 24

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
ir 444 – 447 2

…
…
…
…
…
…
…
…
…

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
ir 444 – 447 2

result 448 – 451
…
…
…
…
…
…
…
…

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
ir 444 – 447 2

result 448 – 451
…
…
…
…
…
…
…
…

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
ir 444 – 447 2

result 448 – 451
ir 468 – 471 1

…
…
…
…
…
…
…

25 26

27 28

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
ir 444 – 447 2

result 448 – 451
ir 468 – 471 1

result 472 – 475
…
…
…
…
…
…

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
ir 444 – 447 2

result 448 – 451
ir 468 – 471 1

result 472 – 475 1
…
…
…
…
…
…

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
ir 444 – 447 2

result 448 – 451
ir 468 – 471 1

result 472 – 475 1
…
…
…
…
…
…

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
ir 444 – 447 2

result 448 – 451
…
…
…
…
…
…
…
…

2 + 1

29 30

31 32

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
ir 444 – 447 2

result 448 – 451 3
…
…
…
…
…
…
…
…

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
ir 444 – 447 2

result 448 – 451 3
…
…
…
…
…
…
…
…

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
…
…
…
…
…
…
…
…
…
…

3 + 3

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447 6
…
…
…
…
…
…
…
…
…
…

33 34

35 36

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447 6
…
…
…
…
…
…
…
…
…
…

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407

…
…
…
…
…
…
…
…
…
…
…
…

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407 6

…
…
…
…
…
…
…
…
…
…
…
…

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407 6

…
…
…
…
…
…
…
…
…
…
…
…

OUTPUT:
Factorial x: 6

37 38

39 40

Recursion in C

END OF Part 2

8-42

How Recursion Works

• What happens when any function is called?
– A call frame is set up
– That call frame is pushed onto the runtime stack

• What happens when a recursive method “calls itself ”?
It’s actually just like calling any other method!
– A call frame is set up
– That call frame is pushed onto the runtime stack

• What happens when any function is called?
– A call frame is set up
– That call frame is pushed onto the runtime stack

• What happens when a recursive method “calls itself ”?
It’s actually just like calling any other method!
– A call frame is set up
– That call frame is pushed onto the runtime stack

8-43

How Recursion Works

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

Label Address Value
399

i 400 – 403 3
x 404 – 407

…
…
…
…
…
…
…
…
…
…
…
…

• What happens when any function is called?
– A call frame is set up
– That call frame is pushed onto the runtime stack

• What happens when a recursive method “calls itself ”?
It’s actually just like calling any other method!
– A call frame is set up
– That call frame is pushed onto the runtime stack

8-44

How Recursion WorksLabel Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
…
…
…
…
…
…
…
…
…
…

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

41 42

43 44

8-45

How Recursion Works

• What happens when any function is called?
– A call frame is set up
– That call frame is pushed onto the runtime stack

• What happens when a recursive method “calls itself ”?
It’s actually just like calling any other method!
– A call frame is set up
– That call frame is pushed onto the runtime stack

• What happens when any function is called?
– A call frame is set up
– That call frame is pushed onto the runtime stack

• What happens when a recursive method “calls itself ”?
It’s actually just like calling any other method!
– A call frame is set up
– That call frame is pushed onto the runtime stack

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

8-46

How Recursion WorksLabel Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
ir 444 – 447 2

result 448 – 451
…
…
…
…
…
…
…
…

• What happens when any function is called?
– A call frame is set up
– That call frame is pushed onto the runtime stack

• What happens when a recursive method “calls itself ”?
It’s actually just like calling any other method!
– A call frame is set up
– That call frame is pushed onto the runtime stack

#include

int SumRec(int );

int main()
{

int i = 3 , x;

x = SumRec(i);
printf(“\nFactorial x: %d\n”, x);

return 0;
}

int SumRec(int ir)
{

int result;
if (ir == 1)
{

reault = 1;
}
else
{

result = (ir + SumRec(ir – 1));
}
return (result);

}

8-47

How Recursion WorksLabel Address Value
399

i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
ir 444 – 447 2

result 448 – 451
ir 468 – 471 1

result 472 – 475 1
…
…
…
…
…
…

8-48

How Recursion Works
• Note: For a recursive function , how many copies of

the code are there?
– Just one! (like any other function )

• When does the recursive function stop calling itself?
– When the base case is reached

• What happens then?
– That invocation of the function completes,

its call frame is popped off the runtime stack,
and

control returns to the function that invoked it

45 46

47 48

8-49

• But which function invoked it?
the previous invocation of the recursive function

– This function now completes,
its call frame is popped off the runtime stack,

and
control returns to the function that invoked it

• And so on until we get back to the first invocation of
the recursive function

How Recursion Works

• But which function invoked it?
the previous invocation of the recursive function

– This function now completes,
its call frame is popped off the runtime stack,

and
control returns to the function that invoked it

• And so on until we get back to the first invocation of
the recursive function

8-50

How Recursion Works
Label Address Value

399
i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
ir 444 – 447 2

result 448 – 451
ir 468 – 471 1

result 472 – 475 1
…
…
…
…
…
…

8-51

• But which function invoked it?
the previous invocation of the recursive function

– This function now completes,
its call frame is popped off the runtime stack,

and
control returns to the function that invoked it

• And so on until we get back to the first invocation of
the recursive function

How Recursion Works
Label Address Value

399
i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
ir 444 – 447 2

result 448 – 451
…
…
…
…
…
…
…
…

8-52

• But which function invoked it?
the previous invocation of the recursive function

– This function now completes,
its call frame is popped off the runtime stack,

and
control returns to the function that invoked it

• And so on until we get back to the first invocation of
the recursive function

How Recursion Works
Label Address Value

399
i 400 – 403 3
x 404 – 407
ir 440 – 443 3

result 444 – 447
…
…
…
…
…
…
…
…
…
…

49 50

51 52

8-53

• But which function invoked it?
the previous invocation of the recursive function

– This function now completes,
its call frame is popped off the runtime stack,

and
control returns to the function that invoked it

• And so on until we get back to the first invocation of
the recursive function

How Recursion Works
Label Address Value

399
i 400 – 403 3
x 404 – 407

…
…
…
…
…
…
…
…
…
…
…
…

8-54

• But which function invoked it?
the previous invocation of the recursive function

– This function now completes,
its call frame is popped off the runtime stack,

and
control returns to the function that invoked it

• And so on until we get back to the first invocation of
the recursive function

How Recursion Works
Label Address Value

399
i 400 – 403 3
x 404 – 407 6

…
…
…
…
…
…
…
…
…
…
…
…

#include

int SumRec(int );

int main()
{

int i = 4 , k;

k = SumRec(i);
printf(“\nFactorial k: %d\n”, x);

return 0;
}

int SumRec(int n)
{

int res;
if (n == 1)
{

rea = 1;
}
else
{

res = (n + SumRec(n – 1));
}
return (res);

}

Recursion in C

END OF Recursion

53 54

55 56

Related Posts