Calculate sum, product, power using recursions

[Tia]

Someone can explain how to think these type of recursion. In this exercise isn't allowed to use arithmetic operators but only recursion.
I don't understand how to get to "sum(pred(n), succ(m))", "sum(prod(pred(n), m), m)", "prod(n, power(n, pred(m)))"
This is the solution

#include <iostream>
using namespace std;

// Functions Declarations

int sum(int n,int m);
int prod (int n,int m);
int power (int n,int m);

// Main

int main () {
    int n,m;
    cout << "n,m= ";
    cin >> n >> m;
    cout << "Sum = " << sum(n,m) << endl;
    cout << "Product = " << prod(n,m) << endl;
    cout << "Power : " << power(n,m) << endl;
}

//Function Definitions

int succ(int i) {
    return (i+1);
}
int pred(int i) {
    return (i-1);
}

int sum(int n, int m){
    if(n==0){
        return m;
    }
    return sum(pred(n), succ(m));
}

int prod(int n, int m){
   if(n==0){
        return 0;
    }
    return sum(prod(pred(n), m), m);
}

int power(int n, int m){
    if(m==0){
        return succ(m);
    }
    return prod(n, power(n, pred(m)));
}

[keskiverto]

A pedantic would note that lines 24 and 27 do use arithmetics operators.


Anyway, have you ever used abacus?
https://en.wikipedia.org/wiki/Abacus

The sum() behaves like abacus. At first you have n and m beads.
Then, on each step, you remove one bead from n and add one bead to m, until n has no beads left.
There will be n steps, because you can take only that many beads from n.
In n steps, n beads are added to the m (one by one). Thus, at end, the latter lot has m+n beads.

There is a loop version of the same:

int sum( int n, int m ) {
  while ( 0 < n ) {
    --n;
    ++m;
  }
  return m;
}

Arithmetics says:

(n + m) == (n-1 + m+1) == (n-2 + m+2) == ... == (0 + m+n)

When your main() calls sum(n,m), the function calls itself recursively, until a call sum( 0, x ) is made, (where x==n+m). That call returns x to the caller (line 32).

Where is the call? On line 34. What is done with the returned value? It is returned as is into the caller of this instance. I.e. the call to sum() that does call sum(0,x) does receive value x and does return it to its own caller. The chain of returns returns from the recursion and thus the main() receives x.


Similarly:

(n * m) == ( ((n-1)*m) + m) == ( (((n-2)*m) + m) + m)

The recursive prod() does in effect expand the multipication into many additions, and then uses the sum() to evaluate it.

[Tia]

Thank you so much. Clear explanation.