Archived

This topic is now archived and is closed to further replies.

recursive help

This topic is 5504 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have to write a recursive function which takes in two parameters (positive ints) with one representing the base of an exponent and the other the power of the exponent. For example exponentialIt(5, 3) would return 125. Any Ideas where to start?

Share this post


Link to post
Share on other sites
Well, this is probably a school assignment so I''m not going to make it too easy.

1. The function body must have a base case when the recursion stops. Otherwise it''ll start calling itself forwer. You know that x^0 = 1, so you just have to check that if the second argument is 0, return 1.

2. Then comes the recursion part. You want to move towards the base case, where the second argument is 0. How? By reducing the second argument by one, naturally. Eventually it becomes 0 and the recursion stops. But whenever you reduce the exponent by one, you must do something special....

Ok.. was I vague enough?-)

Share this post


Link to post
Share on other sites
Where to start, or the function itself? Well here's an idea:


WARNING... complete function follows

EDIT:
Well, nevermind, I took it out. Sorry man, just follow the guy above's tips. It didn't occur to me that it could be an assignment

[edited by - Ronin Magus on November 21, 2002 5:17:49 PM]

Share this post


Link to post
Share on other sites
PS: That was a joke

PPS: Ronin, that might get you a passing grade, but not an "A". Your algorithm is O(N). There''s a O(lgN) solution.

PPPS: We really shouldn''t help people with their homework.

Share this post


Link to post
Share on other sites
Yep, thats right, lg2(n). Consider that exponentiation is reallly like adding, so we want to know how many steps it takes to get to k, where in each step we multiply by some previous result. to get 17 for example, you get:
x, x*x, x^4, x^8, x^16, x^17, and for any exponent k, it will take at most 2lg2(k) -1 one steps. Stoffel, is this algorithm recursive though?
Brendan

Share this post


Link to post
Share on other sites
Our current topic in my programming class just happens to be recursion. Our next assignment consists of 4 different recursive demos, which I will be working on the remainder of the night...so I''ll be in a ''recursive thinking'' mode.

My point is - Give me some time and I''ll have the answer for you (well some psuedo anyway, I''m not going to write the code for you...that''s your job! )

-Q

Share this post


Link to post
Share on other sites
Here''s how to get started.

Suppose I want to calculate 2^16.
2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2=65536. <-- sloooow.

2*2=4
4*4=16
16*16=256
256*256=65536. <-- faaaaast.


Don''t listen to me. I''ve had too much coffee.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Stoffel
<a href="http://www.gamedev.net/community/forums/topic.asp?topic_id=124521">Click here for recursive help</a>


GameDev.net does not properly unwind the call stack! obviously it was written in a language that does not support recursion.

Share this post


Link to post
Share on other sites
Finally got it. Sorry for the wait (was afk for awhile).

Here''s the psuedo:

Exponential Function definition (you''ll have to determine the parameters)

1.) First check the base case: if (exponent is equal to 0). If this is true, then return 1 (since any number raised to the 0th power is 0)
2.) For all other cases, you need to return the base multiplied by result of the previous multiplication. For example:
Using your example, 5 * 5 * 5 = 125
If we work from left to right, evaluating one binary expression at a time, we have:
5 * 5 = 25 and our new return value becomes 25. Now we need to multiply the next number (our base: 5) by the previous result (or, the previous return value).
25 * 5 = 125

I''ll attempt to draw a little diagram here that might explain the recursion better:


125 = 25 * 5
^
|
^--<- | return base * expfuncion(params)-| a
| 25 = 5 * 5 v
^----------<-| return base * expfunction(params)-| b
| 5 = 5 * 1 v
^-------<-|return base * expfunc(params)-| c
| 1 v
^---------------|return base case| d


Well that''s a crude drawing...I hope it displays correctly.

Anyway, I hope this didn''t confuse you further, recursion is not an easy subject to explain if you aren''t familiar with stacked function calls, and the ''wind up / wind down'' way of looking at things.

I also hope I didn''t give too much away here.

Hope this helps you out. It actually helped me out b/c the more I do with recursion, the better I understand it.

-Q

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
While this isn''t the optimal way to compute the value of an exponent, this is an easy way to think about it. Frist off, develop a function to compute x^0. This is easy as x^0 = 1 where x is an integer. Call this function f0(x). Now assume you have a function f(x, k) that properly computes the kth power of x, or x^k. Develop a way of computing the kth+1 power of x, knowing that f(x, k) is correct. Since f(x, k+1) = x^(k+1) = x*x^k = x*f(x, k), we know f(x, k+1) is correct in computing the kth+1 power of x. Now how to program this? Note the two portions of the above:

(i) f0(x) = 1, which is really f(x, 0).
(ii) f(x, k+1) = x*f(x, k), or f(x, k) = x*f(x, k-1).

(i) is known as the base case while (ii) is known as the recursive or inductive step. If you have a few example of recursion handy translating the above into a real function shouldn''t take too long. To help illustrate though, here is what the actual computation would look like:

f(10, 4) -> 10*f(10, 3) -> 10*10*f(10, 2) -> 10*10*10*f(10, 1) -> 10*10*10*10*f(10, 0) -> 10*10*10*10*1 = 10000.

Since you''re obviously new to this, just the basic method of doing it first. Google search for the basics of mathematical induction, as understanding it will make recursion in programming a snap.

Also, if I may soapbox a little, don''t let anyone badmouth recursion based on it''s poor implementation in C/C++/Java. Just because a language doesn''t support proper tail-recursion or first-class and anonymous functions to work around head-recursion doesn''t mean that recursion itself is bad. In fact, all tail-recursive functions can be directly translated into assembly equivalent to a for/while-loop solution. head-recursion can be turned into tail-recursion with the use of anonymous functions/first-class functions/continuations, and is subsequently equivalent to using an explicit stack for arguments as opposed to the system call stack. Algorithms for depth/breadth-first graph traversals do the explicit stack method. Anyways, I''m rambling. Have fun.

Share this post


Link to post
Share on other sites
Languages don''t need to support tail recursion. Compilers do.

The Russian Peasant algorithm is faster than just doing the multiplications, but I suspect it''ll also disclose that you asked for help.

Share this post


Link to post
Share on other sites
To simplify, Mathematical Induction is used to prove a case where if a function returns the correct answer for a base number (in this case, 0) then for all numbers > base the function will return the correct answer.

quote:
Original post by Anonymous Poster
While this isn''t the optimal way to compute the value of an exponent, this is an easy way to think about it. Frist off, develop a function to compute x^0. This is easy as x^0 = 1 where x is an integer. Call this function f0(x). Now assume you have a function f(x, k) that properly computes the kth power of x, or x^k. Develop a way of computing the kth+1 power of x, knowing that f(x, k) is correct. Since f(x, k+1) = x^(k+1) = x*x^k = x*f(x, k), we know f(x, k+1) is correct in computing the kth+1 power of x. Now how to program this? Note the two portions of the above:

(i) f0(x) = 1, which is really f(x, 0).
(ii) f(x, k+1) = x*f(x, k), or f(x, k) = x*f(x, k-1).

(i) is known as the base case while (ii) is known as the recursive or inductive step. If you have a few example of recursion handy translating the above into a real function shouldn''t take too long. To help illustrate though, here is what the actual computation would look like:

f(10, 4) -> 10*f(10, 3) -> 10*10*f(10, 2) -> 10*10*10*f(10, 1) -> 10*10*10*10*f(10, 0) -> 10*10*10*10*1 = 10000.

Since you''re obviously new to this, just the basic method of doing it first. Google search for the basics of mathematical induction, as understanding it will make recursion in programming a snap.

Also, if I may soapbox a little, don''t let anyone badmouth recursion based on it''s poor implementation in C/C++/Java. Just because a language doesn''t support proper tail-recursion or first-class and anonymous functions to work around head-recursion doesn''t mean that recursion itself is bad. In fact, all tail-recursive functions can be directly translated into assembly equivalent to a for/while-loop solution. head-recursion can be turned into tail-recursion with the use of anonymous functions/first-class functions/continuations, and is subsequently equivalent to using an explicit stack for arguments as opposed to the system call stack. Algorithms for depth/breadth-first graph traversals do the explicit stack method. Anyways, I''m rambling. Have fun.




http://roninmagus.hopto.org
acronymfinder.com - Find any acronym you need!

Share this post


Link to post
Share on other sites
Hey Ronin, you have quite a bit of mathmatical knowledge...that much is clear.

But lets not forget that this guy is probably doing this assignment for a beggining-intermediate level programming course, and not an advanced computer science course!!! LOL

I read your thread about a half a dozen times, and am trying to understand it myself. I don''t know if what you are trying to say is obvious and you just didn''t state it clearly, if recursion is far more in depth than I thought.

I''ll definetly look for your name though in any future advanced comp sci quesions I have in the future.

-Q

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:

Languages don''t need to support tail recursion. Compilers do.



Languages often have specifications and/or "features" such that proper tail-recursion is impossible. Java disallows tail-recursion for security reasons and tail-recursion is broken in C/C++ because of the following example:


  
#include <iostream>

int f(int x, int* ptr)
{
if (x == 0) {
return 0;
} else {
std::cout << x << ''\t'' << *ptr << std::endl;
return f(x-1, &x); // note: &x is not the same as ptr

}
}

int main()
{
int y = 5;
f(y, &y);

return 0;
}


When compiled and executed by g++ (not tail-recursive), the above yields:


[MyMachine:~] mylogin% g++ f.cpp -o f
[MyMachine:~] mylogin% ./f
5 5
4 5
3 4
2 3
1 2


If compiled with proper tail-recursion in mind, the same function would yield:


5 5 // note: in this case &x would be equal ptr
4 4 // for each function call
3 3
2 2
1 1


The problem is that you can obtain the address of values on the stack and pass them to other functions. Since tail-recursion involves copying over current stack values, it causes a problem for any pointer that contains the address of a value on the stack. The value will change with each new tail call.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
Languages often have specifications and/or "features" such that proper tail-recursion is impossible.

That isn''t the same thing.

That a language may permit one to write programs that are not tail recursive. Even languages that mandate tail recursion-optimizing compilers permit that (transformation into things with manually managed stacks is missing the point entirely).


quote:
If compiled with proper tail-recursion in mind, the same function would yield:

If it yielded that, it would yield the wrong answer. Even with "proper" tail recursion, modifying the semantics of the function is wrong.



Share this post


Link to post
Share on other sites