Understanding Recursive Functions

Don't quite understand how they work.

Page 1 of 1

10 Replies - 1422 Views - Last Post: 14 December 2009 - 12:51 AM Rate Topic: -----

#1 Cyclone  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 90
  • Joined: 13-February 09

Understanding Recursive Functions

Post icon  Posted 12 December 2009 - 06:19 PM

This example uses a recursive function to find the factorial of the number 4. I used a 'cout' command to try to understand what is going on. But I don't know why the first output is '2'. I tried really hard to create my own logic to undstand why it's doing what it's doing lol. And also read the page in the book a few times but I still don't get it.
#include "stdafx.h"
#include <iostream>
using namespace std;

int factr(int n);
int fact(int n);

int main()
{
	// Use recursive version.
	cout << "factorial is " << factr(4);
	cout << "\n";

	// Use iterative version.
	//cout << "4 factorial is " << fact(4);
	cout << "\n";

	return 0;
}

// Recursive version.
int factr(int n)
{
	int answer;
	if(n==1) {return(1);}
	answer = factr(n-1)*n; //Execute a recursive call to factr().
	
	
	cout << answer << " ";
	return(answer);
}

//Iterative version.
int fact(int n)
{
	int t, answer;

	answer = 1;
	for(t=1; t<=n; t++) {answer = answer*(t);}
	return(answer);
}




Is This A Good Question/Topic? 0
  • +

Replies To: Understanding Recursive Functions

#2 fushar  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 32
  • Joined: 12-December 09

Re: Understanding Recursive Functions

Posted 12 December 2009 - 06:23 PM

It's because the after the deepest call to factr(1), the execution returns to factr(2), and it will print '2' because
answer = factr(1)*n = 1*2 = 2.
factr(1) won't print anything because based on your code it just returns 1.
Was This Post Helpful? 0
  • +
  • -

#3 Cyclone  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 90
  • Joined: 13-February 09

Re: Understanding Recursive Functions

Posted 12 December 2009 - 08:11 PM

So recursive functions work backwards? Or before the statement executes it works backwards untill it reaches some sort of return statement. Once it reaches the 'deepest' part it will work it's way back to the begining while executing the code? Maybe this is why the book said the recursive function will never return if there is no conditional statement. hmm but my logic below still seems flawed. :(

Like this?:

1. factr(1-1)*1 <--- why doesn't it start at zero then?
2. factr(2-1)*2. answer = 2 <--- is ignored due to the conditional statement.
3. factr(3-1)*3. answer = 6
4. factr(4-1)*4. answer = 12
5. Where is the answer of 24? :(

I would have thought the first pass would out put 12 as in my logic.

First pass:
1. the 4 gets passed to the factr(4) function.
2. answer = factr(4-1)*4
4. answer would = 12
5. the cout would then output 12 during the first pass.

Second pass:
1. the 4 gets passed to the factr(4) function.
2. answer = factr(3-1)*12
4. answer would = 24
5. Third pass is ignored because 'n' would = 1.
5. the cout would then output 24 (the final value)

This post has been edited by Cyclone: 12 December 2009 - 08:25 PM

Was This Post Helpful? 0
  • +
  • -

#4 ccubed  Icon User is offline

  • It's That Guy
  • member icon

Reputation: 162
  • View blog
  • Posts: 1,409
  • Joined: 13-June 08

Re: Understanding Recursive Functions

Posted 12 December 2009 - 08:46 PM

Because 0! is 1.

And your logic is backwards. It's like this.

factr(4)
-4 != 1
--return factr(3)*4
---factr(3)
----3 != 1
-----return factr(2)*3
------factr(2)
-------2 != 1
--------return factr(1)*2
---------1 == 1
----------return 1
--------return 1*2
------return 2*3
-----return 6*4
factr(4) returns 6*4 = 12 * 2 = 24


This post has been edited by ccubed: 12 December 2009 - 08:50 PM

Was This Post Helpful? 0
  • +
  • -

#5 fushar  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 32
  • Joined: 12-December 09

Re: Understanding Recursive Functions

Posted 12 December 2009 - 08:47 PM

To become clear, let's trace the execution of factr(4). Indentations are added for clarity. Statements in the same indentation are in the same depth.

begin

factr(4)
	factr(3)
		factr(2)
			factr(1)
				return 1. So factr(1) = 1.
			print answer = 2*factr(1) = 2*1 = 2.
			return answer = 2. So factr(2) = 2.
		print answer = 3*factr(2) = 3*2 = 6.
		return answer = 6. So factr(3) = 6.
	print answer = 4*factr(3) = 4*6 = 24.
	return answer = 24. So factr(4) = 24.

end.

This post has been edited by fushar: 12 December 2009 - 08:47 PM

Was This Post Helpful? 0
  • +
  • -

#6 kidicarus  Icon User is offline

  • D.I.C Head

Reputation: 16
  • View blog
  • Posts: 139
  • Joined: 13-February 09

Re: Understanding Recursive Functions

Posted 12 December 2009 - 10:40 PM

int recursiveFactorial(int y, int x)
{	
	
	using namespace std;
	
	if (x <= 1)
		return y;
	
	//cout << y << "\t" << x <<  endl;
	y = y * x;
	
	recursiveFactorial(y, x - 1);

}


You want to remember that when you call the function again the y value should be updated. This is not the way it is normally programmed but it is pretty close. (Y = 1 at first.)

You could probably set up a default value of 1 for y, and then call the function again and again using two arguments.

lol were you getting infinite loops or was it returning 0.
Was This Post Helpful? 0
  • +
  • -

#7 Mercurial  Icon User is offline

  • D.I.C Head

Reputation: 18
  • View blog
  • Posts: 178
  • Joined: 06-November 09

Re: Understanding Recursive Functions

Posted 12 December 2009 - 11:48 PM

View PostCyclone, on 12 Dec, 2009 - 05:19 PM, said:

This example uses a recursive function to find the factorial of the number 4. I used a 'cout' command to try to understand what is going on. But I don't know why the first output is '2'. I tried really hard to create my own logic to undstand why it's doing what it's doing lol. And also read the page in the book a few times but I still don't get it.
#include "stdafx.h"
#include <iostream>
using namespace std;

int factr(int n);
int fact(int n);

int main()
{
	// Use recursive version.
	cout << "factorial is " << factr(4);
	cout << "\n";

	// Use iterative version.
	//cout << "4 factorial is " << fact(4);
	cout << "\n";

	return 0;
}

// Recursive version.
int factr(int n)
{
	int answer;
	if(n==1) {return(1);}
	answer = factr(n-1)*n; //Execute a recursive call to factr().
	
	
	cout << answer << " ";
	return(answer);
}

//Iterative version.
int fact(int n)
{
	int t, answer;

	answer = 1;
	for(t=1; t<=n; t++) {answer = answer*(t);}
	return(answer);
}





View PostCyclone, on 12 Dec, 2009 - 07:11 PM, said:

Like this?:

1. factr(1-1)*1 <--- why doesn't it start at zero then?
2. factr(2-1)*2. answer = 2 <--- is ignored due to the conditional statement.
3. factr(3-1)*3. answer = 6
4. factr(4-1)*4. answer = 12
5. Where is the answer of 24? :(


It doesn't. You're always passing the value-1, so when your current value of n is 2, you call
answer = factr(n-1)*n;

which is
answer = factr(2-1)*2;
. The program jumps to factr(2-1) function and says:
if(n==1) {return(1);}
and returns the value to the previous function, the one I wrote first. So its
 answer = 1*2 
(the first one is factr(2-1) and the second one is current n).It returns it to the previous function where n was 3 etc. while it reaches the top, the first function you called, with the n you've send from the main() or from wherever you called it.

It can be a bit confusing in the beginning. Just ask if you didn't get it.

This post has been edited by Mercurial: 12 December 2009 - 11:50 PM

Was This Post Helpful? 0
  • +
  • -

#8 Bench  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 857
  • View blog
  • Posts: 2,343
  • Joined: 20-August 07

Re: Understanding Recursive Functions

Posted 13 December 2009 - 02:34 AM

View PostCyclone, on 13 Dec, 2009 - 03:11 AM, said:

1. factr(1-1)*1 <--- why doesn't it start at zero then?
What happens when you multiply a number by zero?

View PostCyclone, on 13 Dec, 2009 - 03:11 AM, said:

2. factr(2-1)*2. answer = 2 <--- is ignored due to the conditional statement.
3. factr(3-1)*3. answer = 6
4. factr(4-1)*4. answer = 12
5. Where is the answer of 24? :(

Check line 4 again:

factr(4-1)*4 is the same as factr(3)*4 is the same as 6 * 4; doesn't equal 12, its 24
Was This Post Helpful? 0
  • +
  • -

#9 Shadi Salameh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 14-May 09

Re: Understanding Recursive Functions

Posted 13 December 2009 - 09:55 AM

NICE

Thank you very much...
Was This Post Helpful? 0
  • +
  • -

#10 Cyclone  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 90
  • Joined: 13-February 09

Re: Understanding Recursive Functions

Posted 14 December 2009 - 12:45 AM

I think I got it now. Does this make any sense? Yes I know I'm over thinking. I'm just trying to make sure I understand it. I'm slow... :rolleyes: :v:

1. Execute recursive function. n=4. Pass the value of 4 to the variable 'n'

2. Find base/bottom:

n = 4
answer = factr(n-1)*n <-- When this statment is first read both the 'n' variables are assigned
the value of 4. Right after this the program will begin executing the
multiple iterations of the factr() function. The 'n' on the right side
will always be 4. The result of factr() will be unknown to this statement
untill all of it's iterations have been completed at which
point it's final result will be multiplied by 4(the value that 'n'
was assinged at the very begining).

Iterations of factr(n-1)*n
(a) factr(4-1)*4
(aa) n = 3
(b ) factr(3-1)*3
(bb) n = 2
(c ) factr(2-1)*2 = 2 which is the result of the factr() in line (b )
(cc) n = 1

Base found (n = 1. Conditional statement met. Stop.) because executing the factr() function in
line © would make 'n' equal one and so the conditional statement would tell this iteration
of the function to return the value of 1. The 'return' statement is similer to the 'break' in
a for loop and so the recursive function will stop searching it's self for the bottom(last
statement)

3. Work back out\to the top:

Take the smallest possible answer from line © which is two and multiply
it by 3(from the previous statement) which will get the vaulue(result)
of line (b ) which will be 6. Now to get the result of line (a) we
need to take the result of the previous line(b ) of 6 and multiply it
by 4 to get the final answer of 24.

There are two passes. One to get to the very inner part of the recursive function and another
to work it's way back out while executing the statments. Executing them in 'steping stone'
like fasion. ex get the result from the inner most statement then use that result to get the
second inner most statement and so on.
Was This Post Helpful? 0
  • +
  • -

#11 Cyclone  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 90
  • Joined: 13-February 09

Re: Understanding Recursive Functions

Posted 14 December 2009 - 12:51 AM

A quote from http://danzig.jct.ac.../recursion.html explaining how recursive functions work.

Quote

Russian Dolls
One of the properties of recursive functions is that a given function call must wait for the following function call to complete its run before it itself can finish. A convenient metaphor would be that of Russian dolls. If you have a set of dolls within dolls and you take them apart you will first open the outermost doll, then the next, and so on till you have opened the innermost doll. Now when you put them back together, you cannot start with the outermost doll. You first must connect the innermost doll and then put it inside the next larger doll, and then connect it. Last of all you will reconnect the outermost doll around all the inner dolls. So too with recusion. You must finish the innermost function call before you can finish the next inner function call. You should see that the first function call (the outermost one) will be the last one to complete.



Thanks to all the posters for your help!

This post has been edited by Cyclone: 14 December 2009 - 12:51 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1