# New to programming, help with recursive functions.

• 09-22-2008
HitchHiker
New to programming, help with recursive functions.
Just started programming in C and I'm using SAMS Teach Yourself C in 21 Days (I'm not holding them do that time frame though!)

Anyway, chapter 5 is all about functions which are fine and I understand. However, they briefly mention recursive functions. Now I understand the theory, the function calling itself until a condition is reached but I just can't follow in me head their example. I'm nearly there but . . . ah!

This is their code from an exercise question, can someone help me understand why the function doesn't return the value of 1 in every case?

Code:

```#include <stdio.h> int three_powered( int power ); main() { int a = 4; int b = 9; printf("\n3 to the power of %d is %d", a, three_powered(a)); printf("\n3 to the power of %d is %d\n", b, three_powered(b)); } int three_powered( int power ) {   if ( power < 1 )     return ( 1 );   else     return( 3 * three_powered( power - 1 ));         }```
• 09-22-2008
kcpilot
Well, look at the function and look at the parameter passed. If the passed parameter was 1, then it would return 1 immediately and quit. Let's say the parameter is 3, so the first part of the "if statement" is ignored and the "else" is executed. Then the next time, the function is "called" with a parameter of 2, and so on until the parameter is 1, and then the execution will stop and the value from the "recursion" is returned.

Clear?
• 09-22-2008
smoking81
Quote:

Originally Posted by HitchHiker
Just started programming in C and I'm using SAMS Teach Yourself C in 21 Days (I'm not holding them do that time frame though!)

Anyway, chapter 5 is all about functions which are fine and I understand. However, they briefly mention recursive functions. Now I understand the theory, the function calling itself until a condition is reached but I just can't follow in me head their example. I'm nearly there but . . . ah!

This is their code from an exercise question, can someone help me understand why the function doesn't return the value of 1 in every case?

Code:

```#include <stdio.h> int three_powered( int power ); main() { int a = 4; int b = 9; printf("\n3 to the power of %d is %d", a, three_powered(a)); printf("\n3 to the power of %d is %d\n", b, three_powered(b)); } int three_powered( int power ) {   if ( power < 1 )     return ( 1 );   else     return( 3 * three_powered( power - 1 ));         }```

when you call three_powered(4):
power<1? NO -- > return 3*three_powered(3);
three_powered(3) --> return 3*three_powered(2);
three_powered(2)--> return 3*three_powered(1);
three_powered(1)-->return 3* three_powered(0);
finally: three_powered(0) since 0<1 returns 1;

NOW YOU GO BACKWARD:
three_powered(0)-->returns 1;
three_powered(1)-->rreturn 3*three_powered(0)=3*1=3
three_powered(2)--> return 3*three_powered(1)= 3*3=9
three_powered(3)-->return 3*three_powered(2)=3*9=27
three_powered(4)-->return 3*three_powered(3)=3*27=81

when you'll understand how the functions are called using the stack it will be easier to understand recursion.. bye!
• 09-22-2008
HitchHiker
Quote:

when you call three_powered(4):
power<1? NO -- > return 3*three_powered(3);
three_powered(3) --> return 3*three_powered(2);
three_powered(2)--> return 3*three_powered(1);
three_powered(1)-->return 3* three_powered(0);
finally: three_powered(0) since 0<1 returns 1;
This is as far as I got. Obviously it returns 1 at the end, couldn't work out how it could return any other value. I think I understand now, seems the book has forgotten to tell me about the stack. Maybe it will go into it later and things will click more.

Thanks.
• 09-22-2008
matsp
Quote:

Originally Posted by HitchHiker
This is as far as I got. Obviously it returns 1 at the end, couldn't work out how it could return any other value. I think I understand now, seems the book has forgotten to tell me about the stack. Maybe it will go into it later and things will click more.

Thanks.

But the value returned in the final step is returned to the previous level, where it is multiplied by 3, which is then returned to the previous level to that, where it is multiplied by 3 (giving nine), and so on, until the actual result is produced at the 4 levels back (81).

--
Mats
• 09-22-2008
MK27
"can someone help me understand why the function doesn't return the value of 1 in every case?"

This is a better question than at first I thought.

Quote:

Originally Posted by kcpilot
If the passed parameter was 1, then it would return 1 immediately and quit. Let's say the parameter is 3, so the first part of the "if statement" is ignored and the "else" is executed. Then the next time, the function is "called" with a parameter of 2, and so on until the parameter is 1, and then the execution will stop and the value from the "recursion" is returned.

In fact that's not true at all. For starters, "if the parameter passed was 1", it still recurses. Also, the execution does not "stop" because of this so that 'the value from the "recursion" is returned'. The return value is a series of mulitplications the final one of which is by one.

If the power is one the return is three times 1. If power is two, the return is 3x3x1. If the power is three, the return is 3 x 3 x 3 x 1.
• 09-22-2008
kcpilot
Mea Culpa --- old age is ruining my eyesight (and my ability to reason logically).