Programming Forums > Application Development > C++

paulmedic555 · Jan 27th, 2005, 3:15 PM

Hi all i have problems to understand recursion

.Here are two programms.Could someone tell me how they work?

1.

#include <stdio.h>

void up_and_down(int);

main( )
{
up_and_down(1);
}

void up_and_down(n);
int n;
{
printf ("Στάδιο %d\n", n);
if (n < 4)
up_and_down(n+1);
printf ("Στάδιο %d\n", n);
}

2.

(Toggle Plain Text)

#include <stdio.h>

int summing(int);

main()
{
int k=0;

k = k + summing(1);
printf("%d\n", k);
}

int summing(n)
int n;
{
int j=0;

if (n++ < 4)
j = summing(n)+ n;
return j;
}

Mjordan2nd · Jan 27th, 2005, 3:53 PM

Sure. The first program basically prints Στάδιο (n) as many times as you've specified by calling the function up_and_down(), which can then call itself as many times as needed.

When up_and_down() is called for the first time from main(), it passes n the value of 1. The function prints: "Στάδιο 1" (without the quotation marks of course). It then checks if n is less than 4. Since its value is only 1, it calls up_and_down() again, except this time passing the value 2 as the argument (remember that n was 1 in the pass, so n+1 is obviously 2). In the second pass, it prints "Στάδιο 2", checks to see whether n is less than 4, which it is, and calls the up_and_down() again, except this time it passes the value 3. The function prints "Στάδιο 3" and check to see if 3 is less than 4. Since it is, it once again calls itself, passing 4 as the parameter. This time the function prints out "Στάδιο 4", checks to see if 4 is less than 4, and since it's not, it prints out "Στάδιο 4" again. After that, the program ends.

The second one is a little more complex. When your function is called from main(), it's passed the value 1, which is assigned to the variable n. It checks to see if n<4, and afterwards it increments n. If n is less than 4 then the function calls itself. In the second pass, the value is 2, and then incrememnted to 3. It also calls itself. The function is called once again, and the value is incremented to 4. This time, since 4 is not less than 4, the value 0 is returned to the third pass (since the value of j was zero). The third pass returns 4 to the 2nd pass, since the third pass returns 0+4 (n + the value returned by the fourth pass [remember, the value of n was incremented from 3 in the statement if(n++<4)]). The 2nd pass returns 7 to the first pass, since the third pass returned 4, which was added to n, which was 3, and the first pass finally returns the value of 7+2, which is 9 (n was 2). It's pretty covoluted so my appologies. Perhaps a program could better explain what I'm trying to say. Run this code. I made minor changes to your second program:

(Toggle Plain Text)

#include <stdio.h>

int summing(int);

main()
{
int k=0;

k = k + summing(1);
printf("%d\n", k);
}

int summing(n)
int n;
{
int j=0;

if (n++ < 4)
{
	j = summing(n)+ n;
	printf("pass #%d returns the value of %d (the value returned by pass #%d + n (n is %d)\n", n-1, j, n, n);
}
else{
printf("pass #%d returns %d\n", n-1, j);}
return j;
}

codetaino · Jan 28th, 2005, 11:40 PM

Check this example to see if you understand recursion.... lets say you want to add all numbers from 1 to any given number... well you can do this with recursion... and it works like this

addnumberuntil(int number){
if (number is equal 0)
return number
else
return number + addnumberuntil(number-1)
}

explaining my pseudocode function called addnumberuntil you can see that it takes the last number you want to add... you can notice that there is an if that says that if number is zero return the number in other words zero.... and if else... add that number... to the result of the function itself called with the number less 1....

this works like this....
lets say i call the function in my main as...

sum = addnumberuntil(3);

the process is... the function is called with the number variable containing the value 3 because is different than zero it will enter the else and return the 3 + the function called with the number 2 because 2 is not zero it will return the 2 + the function called with 1 and until zero that will return just the zero... another way to explain it is like this...

sum = addnumber(3);
sum = 3 + addnumber(2);
sum = 3 + 2 + addnumber(1);
sum = 3 + 2 + 1 + addnumber(0);
sum = 3 + 2 + 1 + 0;
sum = 6;

i hope this can help you understand recursion...

in most languages you need the if to controll the recursion and you will call the same function in just one of the branches of the if... mmm ask me any further questions... sorry for the language... english is not my native language... so... hope my explanation helps you ..... hehehe take care

UPDATE: I know my function is not perfect is just an example.... if you enter -1 or something it will loop until the computer runs out of memory...

kurifu · Jan 29th, 2005, 1:52 AM

What they said... lol

codetaino · Jan 29th, 2005, 10:23 PM

Quote:

Originally Posted by kurifu

What they said... lol

hehehe is dificult to explain recursion

Jan 27th, 2005, 3:15 PM	#1
paulmedic555 Newbie Join Date: Jan 2005 Location: Greece Posts: 18 Rep Power: 0	recursion Hi all i have problems to understand recursion .Here are two programms.Could someone tell me how they work? 1. (Toggle Plain Text) #include <stdio.h> void up_and_down(int); main( ) { up_and_down(1); } void up_and_down(n); int n; { printf ("Στάδιο %d\n", n); if (n < 4) up_and_down(n+1); printf ("Στάδιο %d\n", n); } #include <stdio.h> void up_and_down(int); main( ) { up_and_down(1); } void up_and_down(n); int n; { printf ("Στάδιο %d\n", n); if (n < 4) up_and_down(n+1); printf ("Στάδιο %d\n", n); } 2. (Toggle Plain Text) #include <stdio.h> int summing(int); main() { int k=0; k = k + summing(1); printf("%d\n", k); } int summing(n) int n; { int j=0; if (n++ < 4) j = summing(n)+ n; return j; } #include <stdio.h> int summing(int); main() { int k=0; k = k + summing(1); printf("%d\n", k); } int summing(n) int n; { int j=0; if (n++ < 4) j = summing(n)+ n; return j; }

Jan 27th, 2005, 3:53 PM	#2
Mjordan2nd The Supreme Ruler Join Date: May 2004 Location: Houston Posts: 1,476 Rep Power: 6	Sure. The first program basically prints Στάδιο (n) as many times as you've specified by calling the function up_and_down(), which can then call itself as many times as needed. When up_and_down() is called for the first time from main(), it passes n the value of 1. The function prints: "Στάδιο 1" (without the quotation marks of course). It then checks if n is less than 4. Since its value is only 1, it calls up_and_down() again, except this time passing the value 2 as the argument (remember that n was 1 in the pass, so n+1 is obviously 2). In the second pass, it prints "Στάδιο 2", checks to see whether n is less than 4, which it is, and calls the up_and_down() again, except this time it passes the value 3. The function prints "Στάδιο 3" and check to see if 3 is less than 4. Since it is, it once again calls itself, passing 4 as the parameter. This time the function prints out "Στάδιο 4", checks to see if 4 is less than 4, and since it's not, it prints out "Στάδιο 4" again. After that, the program ends. The second one is a little more complex. When your function is called from main(), it's passed the value 1, which is assigned to the variable n. It checks to see if n<4, and afterwards it increments n. If n is less than 4 then the function calls itself. In the second pass, the value is 2, and then incrememnted to 3. It also calls itself. The function is called once again, and the value is incremented to 4. This time, since 4 is not less than 4, the value 0 is returned to the third pass (since the value of j was zero). The third pass returns 4 to the 2nd pass, since the third pass returns 0+4 (n + the value returned by the fourth pass [remember, the value of n was incremented from 3 in the statement if(n++<4)]). The 2nd pass returns 7 to the first pass, since the third pass returned 4, which was added to n, which was 3, and the first pass finally returns the value of 7+2, which is 9 (n was 2). It's pretty covoluted so my appologies. Perhaps a program could better explain what I'm trying to say. Run this code. I made minor changes to your second program: (Toggle Plain Text) #include <stdio.h> int summing(int); main() { int k=0; k = k + summing(1); printf("%d\n", k); } int summing(n) int n; { int j=0; if (n++ < 4) { j = summing(n)+ n; printf("pass #%d returns the value of %d (the value returned by pass #%d + n (n is %d)\n", n-1, j, n, n); } else{ printf("pass #%d returns %d\n", n-1, j);} return j; } #include <stdio.h> int summing(int); main() { int k=0; k = k + summing(1); printf("%d\n", k); } int summing(n) int n; { int j=0; if (n++ < 4) { j = summing(n)+ n; printf("pass #%d returns the value of %d (the value returned by pass #%d + n (n is %d)\n", n-1, j, n, n); } else{ printf("pass #%d returns %d\n", n-1, j);} return j; } __________________ "Every gun that is made, every warship launched, every rocket signifies, in the final sense, a theft from those who hunger and are not fed, from those who are cold and are not clothed. The world in arms is not spending money alone. It is spending the sweat of its laborers, the genius of its scientists, the hopes of its children." - Dwight D. Eisenhower

Jan 28th, 2005, 11:40 PM	#3
codetaino Programmer Join Date: Jan 2005 Location: Bayamon, Puerto Rico Posts: 71 Rep Power: 4	Check this example to see if you understand recursion.... lets say you want to add all numbers from 1 to any given number... well you can do this with recursion... and it works like this addnumberuntil(int number){ if (number is equal 0) return number else return number + addnumberuntil(number-1) } explaining my pseudocode function called addnumberuntil you can see that it takes the last number you want to add... you can notice that there is an if that says that if number is zero return the number in other words zero.... and if else... add that number... to the result of the function itself called with the number less 1.... this works like this.... lets say i call the function in my main as... sum = addnumberuntil(3); the process is... the function is called with the number variable containing the value 3 because is different than zero it will enter the else and return the 3 + the function called with the number 2 because 2 is not zero it will return the 2 + the function called with 1 and until zero that will return just the zero... another way to explain it is like this... sum = addnumber(3); sum = 3 + addnumber(2); sum = 3 + 2 + addnumber(1); sum = 3 + 2 + 1 + addnumber(0); sum = 3 + 2 + 1 + 0; sum = 6; i hope this can help you understand recursion... in most languages you need the if to controll the recursion and you will call the same function in just one of the branches of the if... mmm ask me any further questions... sorry for the language... english is not my native language... so... hope my explanation helps you ..... hehehe take care UPDATE: I know my function is not perfect is just an example.... if you enter -1 or something it will loop until the computer runs out of memory... __________________ "God bless u all" :) Last edited by codetaino; Jan 28th, 2005 at 11:42 PM.

Jan 29th, 2005, 1:52 AM	#4
kurifu Expert Programmer Join Date: Jul 2004 Location: Halifax, Nova Scotia (Canada) Posts: 784 Rep Power: 5	What they said... lol __________________ Clifford Matthew Roche <geek@cliffordroche.com> Web Hosting: http://www.crd-hosting.com Consulting: http://www.crdev-consulting.com

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)