Thread: recursive calculation

  1. #1
    Registered User
    Join Date
    Nov 2018
    Posts
    12

    recursive calculation

    I have to design a recursive (not iterative)function that allows me to calculate a scalar product of two vectors of n dimensions.Example:
    Code:
    dot_product ({1.5.2.7.3.0}, {3.0,2.5,1.0}, 3)
    returns 14.25.

    variables

    Code:
    a : vector [MAX] of real,
    b : vector [MAX] of real, 
    n: integer real
    Returns a real.
    Any idea of how to do it?
    I'm just starting with C.

    Thanks,

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,122
    Code:
    if ( n == 0 ) {
        return a[0] * b[0];
    } else {
      return a[0] * b[0] + recursive(a+1,b+1,n-1);
    }
    Tada!
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Nov 2018
    Posts
    12
    Ok thanks.

    Now I have to design another recursive function that calculates the positive divisors sum of a number n. The initial call to a function is sum_divisors (n,1). Exemple: calling sum_divisors (6,1) is 12, because the 6 divisors are 6,3,2,1.

    the function is: sum_divisors(n: integer, d:integer): integer.

    Could you help me to develop this code?

    thanks!

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,122
    Well did you understand what was going on in the version I posted.

    Can you for example write the function using a regular for loop?

    Recursion after all is just a disguised loop.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Nov 2018
    Posts
    12
    I think yes.

    Code:
    int sum_div(int n, int j){
        int sum = 0;
        int i;
    
        for (i=1; i<=n; i++){
            if(n%i==0){
                sum = sum +i;
            }
        }
        return sum;
    }
    But not clear to convert it to recursive.

  6. #6
    Registered User
    Join Date
    Feb 2019
    Posts
    697
    An example with the classic factorial function: Writing the routine with a loop you can do something like this (not considering overflows):
    Code:
    unsigned int fact(unsigned int n)
    {
      // 0! == 1
      unsigned int r = 1;
    
      // kept in the loop until n <= 1!
      while ( n > 1 )
      {
        r *= n;
        n = n - 1;
      }
    
      return r;
    }
    The recursive approach is almost the same thing as the loop above, but we have an EXIT-LOOP condition:
    Code:
    unsigned int fact_r(unsigned int n)
    {
      // kept in the loop until n > 1!
      // or EXIT the loop if n <= 1.
      if ( n <= 1 )
        return 1;
    
      return n * fact_r(n - 1);
    }
    Last edited by flp1969; 04-02-2019 at 08:45 AM.

  7. #7
    Registered User
    Join Date
    Nov 2018
    Posts
    12
    The question is that I have to fill the dot spaces of the algoritm:

    //algorithmic notation
    Code:
     int function sum_divisors (int n, int d){
    
    int result;
    if(n = d) {
       result = ...... //I think 1
    } else {
       result = ........
    }   
    if ...... {
         result = ......
    }
    end if
    end if
    return result;
    end function
    The initial function call is doing this way:
    sum_divisors(n,1);
    Sorry, but still not sure how to do it.

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,122
    All recursion boils down to
    - a base case that is trivially solvable
    - a recursive case which provides a partial solution, and one (or more) recursive calls to solve a self-similar sub-problem.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Converting recursive function to tail recursive
    By ajacobs365 in forum C Programming
    Replies: 1
    Last Post: 10-30-2011, 08:15 AM
  2. Make Recursive function 'Tail-Recursive'
    By dp2452 in forum C Programming
    Replies: 7
    Last Post: 12-04-2009, 10:13 AM
  3. Matrice Recursive Determinant Calculation
    By overlord21 in forum C Programming
    Replies: 6
    Last Post: 11-01-2008, 01:41 AM
  4. Matrice Recursive Determinant Calculation
    By overlord21 in forum C Programming
    Replies: 1
    Last Post: 10-31-2008, 10:37 AM
  5. merge sort: recursive is fasfter than non-recursive
    By rio_cat in forum C Programming
    Replies: 8
    Last Post: 12-04-2006, 12:52 AM

Tags for this Thread