Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Need Help on how to write this recursive code

  1. Nov 25, 2006 #1
    write recursive code for the following integer function:

    power(x,n) is the exponential or power function x^n, where n is the exponent

    For example: power(3,4) evaluates 3^4 which is 3 x 3 x 3 x 3 = 81

    Expect the integer result to be large(ie in the millions)

    explain how recursive code works.

    Please help me how to write this code.
  2. jcsd
  3. Nov 25, 2006 #2
    well recusion is a very simple thing - the whole point is that you will be calling the same function again but:
    - the function has a condition at which it will not call itself but return
    - by each call the paramter should get closer to the condition.

    Example: You can define the Factorial function recursively
    btw n!=1*2*...(n-1)*(n)
    e.g. 3!=1*2*3=6

    Now you can get n! = (n-1)!*n

    that is 4! = 3! * 4 = 6*4 = 24

    ok, soo to calculate n! we would call (n-1)! and multiply with n. But there must also be a stopping condition. That will be 0! = 1, the condition at which the method should return 1, other it should call itself with (n-1) parameter. Enough talk, the function would look like this

    Java code:

    public long factorial(long n){

    if(n == 0){
    return 1;
    return factorial(n-1)*n;


    now if you call factorial(3) what whould happen

    factorial(3) calls
    factotrial(2) calls
    factorial(1) calls
    factorial(0) returns 1
    factorial(1) returns 1*1=1
    factorial(2) returns 1*2=2
    factorial(3) returns 2*3=6

    hope this clears things up, if you understand the following method then you know recursion. For more you can take a look a wikipedia.

    Last edited: Nov 25, 2006
  4. Nov 25, 2006 #3

    power(x, 1) is x, which is your "stopping" condition, and it needs to be checked first.

    If n is an even number, power(x, n) is equal to power(x, n/2) squared. Otherwise power(x, n) is equal to x times power(x, n - 1).

    A recursive function has two sections. The first section contains your "stopping" checks where the function just returns a result without calling itself. The second section contains decomposition code where a simplifying recursive expression is used, eventually reaching the stopping condition.
  5. Nov 25, 2006 #4
    Hi Guys,

    Thanks a lot! I got another question:

    using recursive power function to calculate the equation

    y(x,n) = x^n + x^n-1+x^n-2+x^n-3+........x^1 for n>=0

    So the program will be something like

    int x
    long int factorial(int n)
    if (n >=0)
    return(x * factorial (n-1));

    may i know what does return (1) actually means?
    Please advise. Thanks.
  6. Nov 26, 2006 #5
    To compute y(x, n) you just need to figure out the "stopping" condition, and the simplifying expression. The stopping condition is fairly easy, that y(x, 1) is just equal to x. Now for the simplifying expression you can figure that out by yourself.

    int factorial(int n) {
    if (n == 1) return(1);
    else return(n * factorial(n -1));

    Returning 1 just means that factorial(1) should be 1.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook